# Selling Pieces of Wood
**Difficulty:** HARD
[External](https://leetcode.com/problems/selling-pieces-of-wood)
Canonical: https://scaleengineer.com/dsa/problems/selling-pieces-of-wood
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array
**Companies:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
You are given two integers `m` and `n` that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array `prices`, where `prices[i] = [hi, wi, pricei]` indicates you can sell a rectangular piece of wood of height `hi` and width `wi` for `pricei` dollars.

To cut a piece of wood, you must make a vertical or horizontal cut across the **entire** height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to `prices`. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you **cannot** rotate a piece to swap its height and width.

Return _the **maximum** money you can earn after cutting an_ `m x n` _piece of wood_.

Note that you can cut the piece of wood as many times as you want.

**Example 1:**

![](https://assets.glich.co/dsa/selling-pieces-of-wood/image0.png) 

**Input:** m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
**Output:** 19
**Explanation:** The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.

**Example 2:**

![](https://assets.glich.co/dsa/selling-pieces-of-wood/image1.png) 

**Input:** m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
**Output:** 32
**Explanation:** The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.

**Constraints:**

* `1 <= m, n <= 200`
* `1 <= prices.length <= 2 * 104`
* `prices[i].length == 3`
* `1 <= hi <= m`
* `1 <= wi <= n`
* `1 <= pricei <= 106`
* All the shapes of wood `(hi, wi)` are pairwise **distinct**.

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's recursive structure into code. For any piece of wood of size `h x w`, we can either sell it as is, or cut it horizontally or vertically. A recursive function `solve(h, w)` is defined to calculate the maximum price obtainable from a piece of size `h x w` by exploring all possible sequences of cuts.
**Time:** Exponential, likely O((m+n)!). The function branches for each possible cut, and since subproblem results are not saved, the same calculations are repeated many times. This is far too slow for the given constraints. · **Space:** O(m + n) in the worst case for the recursion stack depth.
**Pros:** Simple to understand and implement as it directly models the problem statement.; The logic clearly represents the decision-making process at each step (cut or not cut).
**Cons:** Extremely inefficient due to massive re-computation of the same subproblems. For example, `solve(2,2)` would be calculated multiple times when solving for `solve(3,3)`.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to define a function that calculates the maximum value for a given dimension `(h, w)`. This function considers all choices at each step. First, it considers the option of not cutting the piece at all and selling it for its given price. Then, it iterates through all possible horizontal cuts. For each horizontal cut that splits the `h x w` piece into `i x w` and `(h-i) x w`, it recursively calculates the maximum value for both smaller pieces and sums them up. It does the same for all possible vertical cuts. The function then returns the maximum value among the no-cut option and all possible horizontal and vertical cut options. This process continues until the pieces are too small to be cut further. To facilitate quick price lookups, the input `prices` array is first converted into a 2D array or a hash map.

```java
class Solution {
    private long[][] priceTable;

    public long sellingWood(int m, int n, int[][] prices) {
        priceTable = new long[m + 1][n + 1];
        for (int[] p : prices) {
            priceTable[p[0]][p[1]] = p[2];
        }
        return solve(m, n);
    }

    private long solve(int h, int w) {
        // Option 1: Don't cut, sell as is.
        long maxPrice = priceTable[h][w];

        // Option 2: Horizontal cuts
        for (int i = 1; i < h; i++) {
            maxPrice = Math.max(maxPrice, solve(i, w) + solve(h - i, w));
        }

        // Option 3: Vertical cuts
        for (int j = 1; j < w; j++) {
            maxPrice = Math.max(maxPrice, solve(h, j) + solve(h, w - j));
        }

        return maxPrice;
    }
}
```
### Algorithm
*   Define a recursive function `solve(h, w)` that computes the maximum price for a piece of wood of size `h x w`.
*   The base case for the recursion is when a piece cannot be cut further (e.g., `1x1`), or when we choose not to cut it. The value in this case is simply the price for that specific dimension, if one exists.
*   For a piece of size `h x w`, the function explores three main options:
    1.  **No Cut**: The value is the price given for a piece of size `h x w`.
    2.  **Horizontal Cut**: Iterate through all possible cut positions `i` from `1` to `h-1`. For each `i`, the piece is split into `i x w` and `(h-i) x w`. The total value is the sum of the results from recursively calling the function on these two smaller pieces: `solve(i, w) + solve(h-i, w)`.
    3.  **Vertical Cut**: Similarly, iterate through all possible cut positions `j` from `1` to `w-1`. For each `j`, the piece is split into `h x j` and `h x (w-j)`. The value is `solve(h, j) + solve(h, w-j)`.
*   The function `solve(h, w)` returns the maximum value found among all these possibilities.
*   The final answer is obtained by calling `solve(m, n)`.

## Top-Down Dynamic Programming (Memoization)
This approach enhances the brute-force recursion by incorporating memoization, a key technique in dynamic programming. The idea is to store the results of expensive function calls (subproblems) and return the cached result when the same inputs occur again. This avoids redundant computations and drastically improves efficiency.
**Time:** O(m*n * (m+n)). There are `m*n` states `(h, w)`. Each state is computed once. The computation for a state `(h, w)` involves loops of size `O(h)` and `O(w)`. The total time is `Σ_{h=1 to m} Σ_{w=1 to n} O(h+w) = O(m*n*(m+n))`. · **Space:** O(m * n) for the memoization table. The recursion stack also uses space, but it's dominated by the table size.
**Pros:** Drastically more efficient than brute-force recursion.; Guarantees that each subproblem `(h, w)` is solved only once.; Sufficiently fast to pass the time limits for the given constraints.; The code structure remains intuitive and close to the problem's recursive definition.
**Cons:** Can cause a stack overflow for very large `m` or `n` due to deep recursion, though this is not an issue for the given constraints.; Has a slight overhead compared to the iterative bottom-up approach due to function call mechanics.
### Explanation
We observe that the brute-force recursive solution repeatedly solves the same subproblems. For instance, the maximum value for a `2x2` piece is needed to solve for a `3x2` piece and also for a `2x3` piece. By storing the result for each dimension `(h, w)` after computing it the first time, we can avoid this redundant work. We use a 2D array, `memo`, for this purpose. The recursive function `solve(h, w)` first checks this table. If a result exists, it's returned in O(1) time. Otherwise, the computation proceeds as before, and the new result is saved in the table before being returned. This turns the exponential complexity of the naive recursion into a polynomial one.

```java
import java.util.Arrays;

class Solution {
    private long[][] priceTable;
    private long[][] memo;

    public long sellingWood(int m, int n, int[][] prices) {
        priceTable = new long[m + 1][n + 1];
        for (int[] p : prices) {
            priceTable[p[0]][p[1]] = p[2];
        }
        memo = new long[m + 1][n + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(m, n);
    }

    private long solve(int h, int w) {
        if (memo[h][w] != -1) {
            return memo[h][w];
        }

        long maxPrice = priceTable[h][w];

        // Horizontal cuts (optimized loop)
        for (int i = 1; i <= h / 2; i++) {
            maxPrice = Math.max(maxPrice, solve(i, w) + solve(h - i, w));
        }

        // Vertical cuts (optimized loop)
        for (int j = 1; j <= w / 2; j++) {
            maxPrice = Math.max(maxPrice, solve(h, j) + solve(h, w - j));
        }

        return memo[h][w] = maxPrice;
    }
}
```
### Algorithm
*   Create a memoization table, `memo[m+1][n+1]`, to store the results of subproblems. Initialize it with a sentinel value (e.g., -1).
*   Use the same recursive function `solve(h, w)` as in the brute-force approach.
*   At the beginning of `solve(h, w)`, check if `memo[h][w]` has already been computed (i.e., not the sentinel value). If so, return the stored value immediately.
*   If the value is not in the memo table, compute it by exploring the no-cut, horizontal cut, and vertical cut options, just like in the brute-force method.
*   Before returning the computed maximum price, store it in `memo[h][w]`.
*   The loops for cuts can be slightly optimized. For horizontal cuts, iterating `i` from `1` to `h/2` is sufficient, as `solve(i, w) + solve(h-i, w)` is symmetric. The same applies to vertical cuts.
*   The initial call is `solve(m, n)`.

## Bottom-Up Dynamic Programming
This approach is an iterative, or bottom-up, implementation of the dynamic programming solution. Instead of starting from the main problem and breaking it down recursively, we start from the smallest possible subproblems and build our way up to the solution for the original `m x n` piece. This avoids recursion and its associated overhead.
**Time:** O(m*n * (m+n)). The four nested loops for `h`, `w`, and the cut positions `i` and `j` result in this complexity, which is asymptotically the same as the top-down memoized approach. · **Space:** O(m * n) for the DP table.
**Pros:** Generally the most performant approach in practice due to the absence of recursion overhead.; Avoids any risk of stack overflow errors.; The iterative nature can make memory access patterns more predictable and cache-friendly.
**Cons:** The logic can sometimes be less intuitive to formulate compared to the top-down recursive approach, which more directly mirrors the problem's structure.
### Explanation
We use a 2D array `dp` of size `(m+1) x (n+1)`, where `dp[h][w]` will store the maximum money that can be earned from a piece of wood of size `h x w`. We first initialize this table by setting `dp[h][w]` to the price of selling an `h x w` piece without any cuts. Then, we iterate through all dimensions `(h, w)` from `(1, 1)` up to `(m, n)`. For each `(h, w)`, we update `dp[h][w]` by considering all possible cuts. For horizontal cuts, we check every split point `i` and see if cutting into `i x w` and `(h-i) x w` gives a better price (`dp[i][w] + dp[h-i][w]`). We do the same for vertical cuts. By the time we calculate `dp[h][w]`, all the necessary smaller subproblem values (`dp[i][w]` for `i<h` and `dp[h][j]` for `j<w`) have already been finalized, ensuring the correctness of the calculation.

```java
class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        long[][] dp = new long[m + 1][n + 1];

        // Pre-fill the dp table with the prices of non-cut pieces
        for (int[] p : prices) {
            dp[p[0]][p[1]] = p[2];
        }

        for (int h = 1; h <= m; h++) {
            for (int w = 1; w <= n; w++) {
                // Horizontal cuts
                // Cut h x w into i x w and (h-i) x w
                for (int i = 1; i <= h / 2; i++) {
                    dp[h][w] = Math.max(dp[h][w], dp[i][w] + dp[h - i][w]);
                }

                // Vertical cuts
                // Cut h x w into h x j and h x (w-j)
                for (int j = 1; j <= w / 2; j++) {
                    dp[h][w] = Math.max(dp[h][w], dp[h][j] + dp[h][w - j]);
                }
            }
        }

        return dp[m][n];
    }
}
```
### Algorithm
*   Create a 2D DP table, `dp[m+1][n+1]`, to store the maximum price for each piece size.
*   First, populate the `dp` table with the initial prices. For each `[h, w, price]` in the input `prices`, set `dp[h][w] = price`. This handles the no-cut case.
*   Iterate through all possible piece heights `h` from 1 to `m`.
*   Inside this loop, iterate through all possible piece widths `w` from 1 to `n`.
*   For each `(h, w)`, calculate the maximum price by considering all possible cuts:
    1.  **Horizontal Cuts**: Iterate `i` from 1 to `h/2`. A cut at `i` results in two pieces, `i x w` and `(h-i) x w`. The combined value is `dp[i][w] + dp[h-i][w]`. Update `dp[h][w]` with the maximum value found.
    2.  **Vertical Cuts**: Iterate `j` from 1 to `w/2`. A cut at `j` results in `h x j` and `h x (w-j)` pieces. The combined value is `dp[h][j] + dp[h][w-j]`. Update `dp[h][w]` with the maximum value found.
*   Because we iterate `h` and `w` in increasing order, when we compute `dp[h][w]`, the values for all smaller subproblems (like `dp[i][w]` and `dp[h][j]`) are guaranteed to have already been computed.
*   The final answer is `dp[m][n]`.

# Solutions
### Java

```java
class Solution { private long [][] memo ; private int [][] d ; public long sellingWood ( int m , int n , int [][] prices ) { d = new int [ m + 1 ][ n + 1 ]; memo = new long [ m + 1 ][ n + 1 ]; for ( long [] e : memo ) { Arrays . fill ( e , - 1 ); } for ( int [] p : prices ) { d [ p [ 0 ]][ p [ 1 ]] = p [ 2 ]; } return dfs ( m , n ); } private long dfs ( int m , int n ) { if ( memo [ m ][ n ] != - 1 ) { return memo [ m ][ n ]; } long ans = d [ m ][ n ]; for ( int i = 1 ; i < m / 2 + 1 ; ++ i ) { ans = Math . max ( ans , dfs ( i , n ) + dfs ( m - i , n )); } for ( int i = 1 ; i < n / 2 + 1 ; ++ i ) { ans = Math . max ( ans , dfs ( m , i ) + dfs ( m , n - i )); } memo [ m ][ n ] = ans ; return ans ; } }
```

### Python

```python
class Solution : def sellingWood ( self , m : int , n : int , prices : List [ List [ int ]]) -> int : @ cache def dfs ( h , w ): ans = d [ h ]. get ( w , 0 ) for i in range ( 1 , h // 2 + 1 ): ans = max ( ans , dfs ( i , w ) + dfs ( h - i , w )) for i in range ( 1 , w // 2 + 1 ): ans = max ( ans , dfs ( h , i ) + dfs ( h , w - i )) return ans d = defaultdict ( dict ) for h , w , p in prices : d [ h ][ w ] = p return dfs ( m , n )
```

### CPP

```cpp
using ll = long long ; class Solution { public: long long sellingWood ( int m , int n , vector < vector < int >>& prices ) { vector < vector < ll >> memo ( m + 1 , vector < ll > ( n + 1 , - 1 )); vector < vector < int >> d ( m + 1 , vector < int > ( n + 1 )); for ( auto & p : prices ) d [ p [ 0 ]][ p [ 1 ]] = p [ 2 ]; return dfs ( m , n , d , memo ); } ll dfs ( int m , int n , vector < vector < int >>& d , vector < vector < ll >>& memo ) { if ( memo [ m ][ n ] != - 1 ) return memo [ m ][ n ]; ll ans = d [ m ][ n ]; for ( int i = 1 ; i < m / 2 + 1 ; ++ i ) ans = max ( ans , dfs ( i , n , d , memo ) + dfs ( m - i , n , d , memo )); for ( int i = 1 ; i < n / 2 + 1 ; ++ i ) ans = max ( ans , dfs ( m , i , d , memo ) + dfs ( m , n - i , d , memo )); memo [ m ][ n ] = ans ; return ans ; } };
```