Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

2312. Selling Pieces of Wood - Leetcode Solution

Code Implementation

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        price_map = {(h, w): p for h, w, p in prices}
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # Option 1: sell as whole, if possible
                dp[i][j] = price_map.get((i, j), 0)
                # Option 2: cut horizontally
                for k in range(1, i // 1):
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])
                # Option 3: cut vertically
                for k in range(1, j // 1):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])
        return dp[m][n]
      
class Solution {
public:
    int sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        unordered_map<int, unordered_map<int, int>> priceMap;
        for (auto& p : prices) {
            priceMap[p[0]][p[1]] = p[2];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = priceMap[i][j];
                for (int k = 1; k < i; ++k) {
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
                for (int k = 1; k < j; ++k) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
            }
        }
        return dp[m][n];
    }
};
      
class Solution {
    public int sellingWood(int m, int n, int[][] prices) {
        int[][] dp = new int[m + 1][n + 1];
        Map<String, Integer> priceMap = new HashMap<>();
        for (int[] p : prices) {
            priceMap.put(p[0] + "," + p[1], p[2]);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = priceMap.getOrDefault(i + "," + j, 0);
                for (int k = 1; k < i; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
                for (int k = 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
            }
        }
        return dp[m][n];
    }
}
      
var sellingWood = function(m, n, prices) {
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    const priceMap = new Map();
    for (const [h, w, p] of prices) {
        priceMap.set(h + ',' + w, p);
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = priceMap.get(i + ',' + j) || 0;
            for (let k = 1; k < i; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
            for (let k = 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }
    return dp[m][n];
};

Problem Description

You are given a rectangular piece of wood of size m by n. You can sell certain sub-rectangles of this wood for a given price, specified in the list prices. Each element of prices is a triple [height, width, price], indicating that a piece of wood with those dimensions can be sold for that price. You can cut the wood into any number of pieces by making horizontal or vertical cuts, and you may sell any number of pieces (including multiple of the same size, if you can cut them out). Your goal is to maximize the total profit by cutting and selling the wood.
  • You can only sell rectangles of sizes specified in prices.
  • You may cut the wood as many times as you like, in any order, to create sellable pieces.
  • You may also choose to not cut and sell the whole piece if it matches a size in prices.
  • Find the maximum total profit you can obtain.

Thought Process

To solve this problem, let's first think about the naive approach. We could try every way to cut the wood, recursively trying all possible horizontal and vertical cuts, and for each resulting piece, see if we can sell it or cut it further. However, this approach quickly becomes infeasible for large m and n because the number of ways to cut grows exponentially. A better approach is to use dynamic programming. The key insight is that the optimal way to cut and sell a piece of wood of size i x j depends only on the optimal ways to cut and sell its smaller sub-rectangles. By storing the results for each sub-rectangle, we avoid recalculating the same values repeatedly. This is a classic "optimal substructure" and "overlapping subproblems" scenario, which are ideal for dynamic programming.

Solution Approach

We will use a 2D dynamic programming table dp, where dp[i][j] represents the maximum profit obtainable from a rectangle of size i x j.
  1. Initialization:
    • Create a map or hash table (price_map) from the prices list for quick lookup of the price for each sellable size.
    • Initialize dp[i][j] to 0 for all i and j.
  2. Filling the DP Table:
    • Iterate over all possible heights i (from 1 to m) and widths j (from 1 to n).
    • If (i, j) is a sellable size (exists in price_map), set dp[i][j] to its sell price.
    • Consider all possible horizontal cuts (cutting at row k, where 1 ≤ k < i), and update dp[i][j] as the maximum of its current value and dp[k][j] + dp[i-k][j].
    • Similarly, consider all possible vertical cuts (cutting at column k, where 1 ≤ k < j), and update dp[i][j] as the maximum of its current value and dp[i][k] + dp[i][j-k].
  3. Result: The answer is dp[m][n], the maximum profit for the original piece.
This approach ensures that for each sub-rectangle, we always know the best way to cut and sell it, either as a whole (if possible) or as the sum of its best sub-pieces.

Example Walkthrough

Suppose m = 3, n = 5, and prices = [[3,5,10],[1,1,2],[2,2,7],[1,2,3]].
  1. The whole piece (3x5) can be sold for 10.
  2. We fill dp for all smaller rectangles:
    • For 1x1, price is 2.
    • For 2x2, price is 7.
    • For 1x2, price is 3.
  3. For each cell, we consider all possible cuts:
    • For example, dp[2][2] could be sold whole (7), or cut into two 1x2 pieces (each worth 3), for a total of 6. So we keep 7.
    • For dp[3][5], we check all possible horizontal and vertical cuts. For instance, cutting horizontally at 1 gives dp[1][5] + dp[2][5]. We compute these recursively using previously filled values.
  4. The final answer is the maximum of selling the whole piece (10), or the best combination of cuts and sells (which, in this example, is 12).

Time and Space Complexity

  • Brute-force approach: Exponential time, because each cut leads to two new subproblems, and the number of ways to cut grows rapidly.
  • Dynamic programming approach:
    • There are O(mn) subproblems (dp[i][j] for each i and j).
    • For each subproblem, we check up to O(m + n) possible cuts (all possible horizontal and vertical cuts).
    • Thus, total time complexity is O(mn(m + n)).
    • Space complexity is O(mn) for the dp table.

Summary

This problem is an excellent example of using dynamic programming to optimize over all possible ways to divide a structure (in this case, a rectangle) into smaller parts. The key insights are to:
  • Model the problem using subproblems (dp[i][j] for each rectangle size).
  • Use memoization to avoid redundant calculations.
  • Carefully consider all possible cuts, and whether it’s better to sell a piece whole or cut it further.
The solution is elegant because it systematically builds up the answer for larger rectangles using solutions to smaller ones, ensuring optimality at each step.