Selling Pieces of Wood
HardPrompt
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:
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:
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 <= 2001 <= prices.length <= 2 * 104prices[i].length == 31 <= hi <= m1 <= wi <= n1 <= pricei <= 106- All the shapes of wood
(hi, wi)are pairwise distinct.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a recursive function
solve(h, w)that computes the maximum price for a piece of wood of sizeh 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:- No Cut: The value is the price given for a piece of size
h x w. - Horizontal Cut: Iterate through all possible cut positions
ifrom1toh-1. For eachi, the piece is split intoi x wand(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). - Vertical Cut: Similarly, iterate through all possible cut positions
jfrom1tow-1. For eachj, the piece is split intoh x jandh x (w-j). The value issolve(h, j) + solve(h, w-j).
- No Cut: The value is the price given for a piece of size
- The function
solve(h, w)returns the maximum value found among all these possibilities. - The final answer is obtained by calling
solve(m, n).
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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 forsolve(3,3).Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
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.
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 ifmemo[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
ifrom1toh/2is sufficient, assolve(i, w) + solve(h-i, w)is symmetric. The same applies to vertical cuts. - The initial call is
solve(m, n).
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
morndue 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.
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.
Algorithm
- Create a 2D DP table,
dp[m+1][n+1], to store the maximum price for each piece size. - First, populate the
dptable with the initial prices. For each[h, w, price]in the inputprices, setdp[h][w] = price. This handles the no-cut case. - Iterate through all possible piece heights
hfrom 1 tom. - Inside this loop, iterate through all possible piece widths
wfrom 1 ton. - For each
(h, w), calculate the maximum price by considering all possible cuts:- Horizontal Cuts: Iterate
ifrom 1 toh/2. A cut atiresults in two pieces,i x wand(h-i) x w. The combined value isdp[i][w] + dp[h-i][w]. Updatedp[h][w]with the maximum value found. - Vertical Cuts: Iterate
jfrom 1 tow/2. A cut atjresults inh x jandh x (w-j)pieces. The combined value isdp[h][j] + dp[h][w-j]. Updatedp[h][w]with the maximum value found.
- Horizontal Cuts: Iterate
- Because we iterate
handwin increasing order, when we computedp[h][w], the values for all smaller subproblems (likedp[i][w]anddp[h][j]) are guaranteed to have already been computed. - The final answer is
dp[m][n].
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 )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 ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.