{x}
blog image

Selling Pieces of Wood

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 <= 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.

Solution Explanation: Selling Pieces of Wood

This problem asks for the maximum amount of money you can earn by cutting a rectangular piece of wood into smaller pieces and selling them according to a given price list. We can solve this using either memoization (top-down dynamic programming) or dynamic programming (bottom-up). Both approaches have the same time and space complexity.

Approach: Dynamic Programming (Both Memoization and DP)

The core idea is to recursively explore all possible ways to cut the wood. For each cut, we consider the maximum profit obtainable from the resulting sub-rectangles. To avoid redundant calculations, we use either memoization (storing results of subproblems) or dynamic programming (iteratively building up solutions from smaller subproblems).

  1. Initialization:

    • Create a 2D array d (or a hashmap equivalent in some languages) to store the prices of rectangular pieces directly from the prices input. d[h][w] stores the price of a piece with height h and width w. If no such piece exists in prices, the value will be 0.
    • Create a 2D array f (or a hashmap equivalent) to store the maximum profit for different sized wood pieces. f[h][w] stores the maximum profit obtainable from a h x w piece of wood.

  2. Iteration (Dynamic Programming):

    • We iterate through all possible heights (h) and widths (w) from 1 to m and 1 to n respectively.
    • For each f[h][w], we consider two types of cuts:
      • Vertical Cuts: We iterate through possible vertical cut positions (k) from 1 to h - 1. The maximum profit is the sum of the profits from the top and bottom parts: max(f[h][w], f[k][w] + f[h - k][w]).
      • Horizontal Cuts: We iterate through possible horizontal cut positions (k) from 1 to w - 1. The maximum profit is the sum of the profits from the left and right parts: max(f[h][w], f[h][k] + f[h][w - k]).
    • We update f[h][w] with the maximum profit found among the initial price (d[h][w]) and the profits from vertical and horizontal cuts.

  3. Memoization (Top-Down Dynamic Programming):

    • Instead of iterating, we use a recursive function dfs(h, w) that computes f[h][w].
    • The base case is when h or w is 0, returning 0.
    • If f[h][w] has already been computed (i.e., it's not -1 or null, depending on the language), we return the stored value.
    • Otherwise, we compute f[h][w] as described in step 2 above and store it before returning.

  4. Result:

    • The maximum profit for the original m x n piece of wood is stored in f[m][n].

Time and Space Complexity

  • Time Complexity: O(m * n * (m + n) + p), where m and n are the dimensions of the wood and p is the number of price entries. The dominant factor is the nested loops in both DP and memoization that explore all possible cuts.

  • Space Complexity: O(m * n). We use a 2D array f (and potentially d) to store the results, using O(m*n) space.

Code Examples

The code examples in Python, Java, C++, Go, and TypeScript are already provided in the problem statement. They implement either memoization or dynamic programming as described above. The choice between memoization and DP is often a matter of preference; memoization can be more concise for some, while DP is often considered slightly more efficient in some cases due to avoiding function call overhead.