2312. Selling Pieces of Wood


Problem Description

You are tasked with cutting a piece of wood to make the maximum amount of money possible. The wood is a rectangle of given height m and width n. There's a list of different dimensions that specific pieces can be sold for, and each dimension has an associated price. These dimensions and prices are presented in a 2D integer array 'prices', with each entry being a triplet [h_i, w_i, price_i], signifying that a piece of wood of height h_i and width w_i can be sold for price_i dollars.

You can split the original piece of wood vertically or horizontally, creating two smaller pieces at each cut, and you can continue to cut the smaller pieces recursively in the same manner. After cutting the wood into smaller pieces, you can sell some or all of the pieces at the prices listed for their respective dimensions. However, the wood has a grain that must be respected, preventing you from rotating pieces to interchange their dimensions.

You need to find the most profitable way to cut the original m x n rectangular piece of wood by possibly selling some of the resulting smaller pieces. You can cut and sell the pieces in any quantity as long as they match the dimensions listed in the 'prices' array.

Intuition

The problem requires maximizing the profit from cutting and selling pieces of the original wood. This implies that we need to consider every possible way of cutting the wood to figure out the best strategy. To do this efficiently, we employ a dynamic programming (DP) approach, where we remember the results (memoization) of the best way to cut smaller pieces to avoid recalculating them multiple times.

The intuition behind the solution is to consider each piece of wood that we cut, from the original down to the smallest possible, and check all the ways it can be cut further. We can do this recursively by defining a function dfs(h, w) that returns the maximum price obtainable from a piece of wood with height h and width w.

In this recursive approach, at each step, we try cutting the piece horizontally at all possible heights and vertically at all possible widths. After each cut, we have two smaller pieces, and we recursively calculate the maximum price we can get from both parts combined by calling dfs() on each of them and summing their values. We do this for all possible cuts and return the maximum sum obtained. We also make sure to check if we can sell the current piece without any cuts, which is why we check the 'prices' dictionary for a direct match.

The use of the cache decorator from the functools module in Python allows us to memoize the results of the dfs function, so we do not recompute the value for the same height and width combination multiple times. The 'd' dictionary is used to map directly from the piece's dimensions to its price for quick look-ups.

The main idea boils down to exploring every cutting possibility and remembering the maximum profit for each piece's dimensions, effectively building a solution from the bottom up.

Learn more about Memoization and Dynamic Programming patterns.

Solution Approach

The solution leverages a top-down dynamic programming approach using recursion with memoization. Here's how the implementation unfolds:

  1. Memoization with cache Decorator: The cache decorator from the functools module allows the function dfs to cache the results of subproblems (i.e., smaller wood pieces). This means that once a dfs(h, w) calculation is made, it doesn't need to be recalculated when the same dimensions are encountered again in the recursion.

  2. Recursive Function dfs: The recursive function dfs(h, w) computes the maximum price that can be obtained for a piece of wood of height h and width w. It’s defined within the sellingWood method so it can access the d dictionary for prices.

  3. Dictionary of Prices d: A dictionary d, where d[h][w] is the price of a piece of wood of height h and width w. The dictionary is a defaultdict of dicts so that we can easily refer to d[h].get(w, 0), which returns 0 if there is no direct price listed for such a dimension. This hashing structure allows for speedy lookups during the recursion.

  4. Initialization of Answer ans: Each call of dfs(h, w) starts by attempting to find if the current dimensions of the wood piece have a price listed. If so, it initializes the value of ans with this price or 0 if such dimensions are not present in d.

  5. Exploring Horizontal and Vertical Cuts: The function then iterates over all possible horizontal cuts (for i in range(1, h // 2 + 1)) and vertical cuts (for i in range(1, w // 2 + 1)), making recursive calls to dfs on the resulting two pieces. It sums the values from both pieces and updates ans if this sum is greater than the current ans.

    • Horizontal cut leads to pieces dfs(i, w) and dfs(h - i, w)
    • Vertical cut leads to pieces dfs(h, i) and dfs(h, w - i)

Each loop iteration effectively simulates one straight cut across the entire dimension of the wood; each possible cut is considered this way.

  1. Returning the Maximum Price: After iterating through all potential cuts, ans will hold the maximum price obtainable for the dimensions h and w. The function returns ans, contributing to the recursive construction of the solution.

  2. Final Return Call: The method sellingWood finishes by returning the result of dfs(m, n), which represents the maximum money that can be earned from the original piece of wood with dimensions m x n.

The use of these patterns - recursion, memoization, intelligent brute force with pruning of unnecessary recalculations, and a clear dictionary-based structure for instant access to known prices - all come together to create an efficient solution to the problem of maximizing the profit obtained from cutting a piece of wood into salable parts.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider a small example to illustrate the solution approach using the dynamic programming method outlined above. Suppose we have a piece of wood of height m = 4 and width n = 4, and we have the following list of prices for certain dimensions:

1prices = [[1, 4, 5], [4, 1, 5], [2, 2, 7], [4, 4, 20]]

Here, a 1 x 4 piece of wood can be sold for 5,a4x1piecefor5, a `4 x 1` piece for 5, a 2 x 2 piece for 7,anda4x4piecefor7, and a `4 x 4` piece for 20.

Following the dynamic programming approach:

  1. Setup: First, we initialize our dictionary d based on the prices given.
1d = {1: {4: 5}, 4: {1: 5, 4: 20}, 2: {2: 7}}
  1. Base Cases: If we try to sell the original piece of 4 x 4 without any cuts, we look into the dictionary d and find d[4][4] = 20. So, without making any cuts, we can get a maximum profit of $20.

  2. Recursion with Cuts:

    • Let's try to make horizontal and vertical cuts to see if we can get more profit.
    • First, a horizontal cut after 1 unit would give us two pieces: 1 x 4 and 3 x 4. There is a price for 1 x 4, which is $5. We don't have a price for 3 x 4; thus, we need to cut it further.
    • If we cut the 3 x 4 piece again horizontally at 1, we end up with a 1 x 4 (5fromthepricestable)anda2x4(whichwecantsellasis,butcancutfurtherintotwo2x2pieces,eachsoldfor5 - from the prices table) and a `2 x 4` (which we can't sell as is, but can cut further into two `2 x 2` pieces, each sold for 7, making $14 together).
    • For the vertical cuts, we'll have similar scenarios, and we recursively apply the same logic.
  3. Comparing Results:

    • In each recursive step, we sum the profit from cutting and compare it with the current maximum. If a cut yields a higher sum, we update our answer ans.
    • In this example, if we sell the 4 x 4 piece as is, we’ll get 20.Butifwecutitas1x4+3x4,andthenthelatterinto1x4+2x4,andfurtherthe2x4intotwo2x2pieces,wewillobtain20. But if we cut it as `1 x 4` + `3 x 4`, and then the latter into `1 x 4` + `2 x 4`, and further the `2 x 4` into two `2 x 2` pieces, we will obtain 5 + 5+5 + 14 = $24.
  4. Iterating Through All Cuts:

    • We iterate over all possible combinations of horizontal and vertical cuts, neither of which will give more than $24, so that’s our maximum possible profit.
  5. Memoization:

    • As we figure out the best cuts, our function dfs uses the @cache decorator to remember the profits for every smaller piece's dimensions to avoid recalculating them later.
  6. Returning the Maximum Profit:

    • After testing all possible cuts, we find that the best strategy to maximize profit is to cut the 4 x 4 piece of wood into one 1 x 4 piece and a 3 x 4 piece, and then further cut the 3 x 4 piece into a 1 x 4 and a 2 x 4 piece, with the 2 x 4 being cut into two 2 x 2 pieces. This strategy gives us the maximum profit of $24 from the original 4 x 4 piece.
    • The result returned by dfs(4, 4) would be $24, which is the maximum money that can be earned from this piece of wood.

By employing this recursive method with memoization, we've navigated through the various cutting strategies, quickly ignored unprofitable paths, and found the most profitable way to cut and sell the original piece of wood.

Solution Implementation

1from functools import lru_cache  # lru_cache is used for memoization.
2from collections import defaultdict  # defaultdict for initializing dictionary values.
3
4class Solution:
5    def sellingWood(self, height: int, width: int, price_list: list) -> int:
6        # A memoized helper function to calculate the maximum price.
7        @lru_cache(maxsize=None)
8        def dfs(current_height, current_width):
9            # Initialize the answer for current piece (height x width).
10            # Check if there's a direct price for the current piece and use it as a starting point.
11            max_price = height_price_mapping[current_height].get(current_width, 0)
12
13            # Recursively cut the piece horizontally and compare to find the max price.
14            for i in range(1, current_height // 2 + 1):
15                price_horizontal_cut = dfs(i, current_width) + dfs(current_height - i, current_width)
16                max_price = max(max_price, price_horizontal_cut)
17
18            # Recursively cut the piece vertically and compare to find the max price.
19            for i in range(1, current_width // 2 + 1):
20                price_vertical_cut = dfs(current_height, i) + dfs(current_height, current_width - i)
21                max_price = max(max_price, price_vertical_cut)
22
23            # Return the maximum price that can be obtained from the current piece.
24            return max_price
25
26        # Dictionary to hold heights as keys and another dictionary as value,
27        # which maps widths to prices.
28        height_price_mapping = defaultdict(dict)
29        for height, width, price in price_list:
30            height_price_mapping[height][width] = price
31
32        # Kick off the recursive function with the full size of the wood piece.
33        return dfs(height, width)
34
1import java.util.Arrays;
2
3class Solution {
4    private long[][] memo; // Table to memoize the results of subproblems
5    private int[][] priceTable; // To store the prices for wooden pieces of different sizes
6
7    // Calculates the maximum amount of money that can be earned by selling wooden pieces
8    public long sellingWood(int m, int n, int[][] prices) {
9        priceTable = new int[m + 1][n + 1];
10        memo = new long[m + 1][n + 1];
11      
12        // Initialize memo table with -1 to indicate uncalculated subproblems
13        for(long[] row : memo) {
14            Arrays.fill(row, -1);
15        }
16      
17        // Fill in the priceTable with given prices
18        for(int[] price : prices) {
19            priceTable[price[0]][price[1]] = price[2];
20        }
21      
22        // Start the Depth-First Search (DFS) from the full size
23        return dfs(m, n);
24    }
25
26    // DFS to calculate the maximum price with the given m x n size
27    private long dfs(int height, int width) {
28        // If we have already calculated this subproblem, return the result
29        if(memo[height][width] != -1) {
30            return memo[height][width];
31        }
32      
33        // Initialize the maximum price with direct sale price or 0 if not sellable directly
34        long maxPrice = priceTable[height][width];
35      
36        // Divide the plate vertically, and try every possible split point
37        for(int i = 1; i <= height / 2; ++i) {
38            maxPrice = Math.max(maxPrice, dfs(i, width) + dfs(height - i, width));
39        }
40      
41        // Divide the plate horizontally, and try every possible split point
42        for(int i = 1; i <= width / 2; ++i) {
43            maxPrice = Math.max(maxPrice, dfs(height, i) + dfs(height, width - i));
44        }
45      
46        // Save the maximum price in the memo table before returning
47        memo[height][width] = maxPrice;
48        return maxPrice;
49    }
50}
51
1using ll = long long; // Define ll as an alias for long long data type.
2
3class Solution {
4public:
5    long long sellingWood(int height, int width, vector<vector<int>>& prices) {
6        // Initialize a 2D vector for memoization, filled with -1.
7        vector<vector<ll>> memo(height + 1, vector<ll>(width + 1, -1));
8      
9        // Initialize a 2D vector for storing the prices with dimensions provided.
10        vector<vector<int>> priceTable(height + 1, vector<int>(width + 1, 0));
11        // Store the given prices in the priceTable.
12        for (auto& price : prices) {
13            priceTable[price[0]][price[1]] = price[2];
14        }
15      
16        // Perform Depth-First Search to find the maximum selling price.
17        return dfs(height, width, priceTable, memo);
18    }
19
20    // Helper function to perform the Depth-First Search.
21    ll dfs(int height, int width, vector<vector<int>>& priceTable, vector<vector<ll>>& memo) {
22        // If the result has been computed before, return the stored value.
23        if (memo[height][width] != -1) return memo[height][width];
24
25        // Initialize the answer with the direct price of the current dimension if available, or zero.
26        ll maxPrice = priceTable[height][width];
27      
28        // Try splitting the wood vertically and find the maximum price.
29        for (int i = 1; i <= height / 2; ++i) {
30            maxPrice = max(maxPrice, dfs(i, width, priceTable, memo) + dfs(height - i, width, priceTable, memo));
31        }
32      
33        // Try splitting the wood horizontally and find the maximum price.
34        for (int i = 1; i <= width / 2; ++i) {
35            maxPrice = max(maxPrice, dfs(height, i, priceTable, memo) + dfs(height, width - i, priceTable, memo));
36        }
37
38        // Store the computed result in the memoization table.
39        memo[height][width] = maxPrice;
40
41        // Return the maximum price.
42        return maxPrice;
43    }
44};
45
1// Define type alias for long long data type.
2type ll = BigInt;
3
4// 2D array type definition for readability
5type Matrix = number[][];
6type BigMatrix = ll[][];
7
8// Define the sellingWood function globally
9function sellingWood(height: number, width: number, prices: Matrix): ll {
10    // Initialize a 2D array for memoization, filled with -1n (BigInt)
11    const memo: BigMatrix = Array.from({length: height + 1}, () =>
12      Array(width + 1).fill(-1n));
13
14    // Initialize a 2D array for storing the prices with given dimensions
15    const priceTable: Matrix = Array.from({length: height + 1}, () =>
16      Array(width + 1).fill(0));
17
18    // Store the given prices in the priceTable
19    prices.forEach((price: number[]) => {
20        priceTable[price[0]][price[1]] = price[2];
21    });
22
23    // Perform Depth-First Search to find the maximum selling price
24    return dfs(height, width, priceTable, memo);
25}
26
27// Helper function to perform the Depth-First Search, defined globally
28function dfs(height: number, width: number, priceTable: Matrix, memo: BigMatrix): ll {
29    // If the result has been computed before, return the stored value
30    if (memo[height][width] !== -1n) return memo[height][width];
31
32    // Initialize the answer with the direct price of the current dimensions if available, or zero
33    let maxPrice: ll = BigInt(priceTable[height][width]);
34
35    // Try splitting the wood vertically and find the maximum price
36    for (let i = 1; i <= Math.floor(height / 2); i++) {
37        maxPrice = max(maxPrice, dfs(i, width, priceTable, memo) + dfs(height - i, width, priceTable, memo));
38    }
39
40    // Try splitting the wood horizontally and find the maximum price
41    for (let i = 1; i <= Math.floor(width / 2); i++) {
42        maxPrice = max(maxPrice, dfs(height, i, priceTable, memo) + dfs(height, width - i, priceTable, memo));
43    }
44
45    // Store the computed result in the memoization array
46    memo[height][width] = maxPrice;
47
48    // Return the maximum price
49    return maxPrice;
50}
51
52// Helper function for max comparison of BigInts
53function max(a: ll, b: ll): ll {
54    return a > b ? a : b;
55}
56

Time and Space Complexity

Time Complexity

The time complexity of the sellingWood function is mainly determined by the number of states that the dynamic programming will compute and how many operations it performs for each state. Since this function uses a top-down dynamic programming approach with memoization (enabled by the @cache decorator), each possible state is only computed once.

The number of states here is proportional to the number of possible subproblems, which is the number of ways we can split the height and width of the wood. Each piece of wood can have a height and width ranging from 1 to m and 1 to n, respectively, resulting in O(m * n) states.

At each state (h, w), the function performs two loops: the first one splits the height and the second one splits the width. The former ranges up to h // 2 and the latter up to w // 2 for each state. Therefore, in the worst-case scenario, the function will do h/2 + w/2 comparisons.

Putting it all together, the worst-case time complexity is:

O(m * n * (m/2 + n/2))

However, as this is an overestimation considering the recurrence relation, a tighter bound would likely be better expressed by considering the height and width are divided in various splits, yet the exact time complexity can be difficult to define without a closed form for the recurrence, particularly due to the effects of memoization.

Space Complexity

The space complexity is determined by the maximum size of the call stack due to recursion and the space used for memoization.

  1. Each recursive call requires space on the call stack until the base case is reached. In the worst case, the call stack could grow linearly with min(m, n) if only one of the dimensions were always split into a single unit piece along with the maximum other dimension.

  2. The memoization cache will store a result for each unique (h, w) combination. Therefore, in the worst case, it will store O(m * n) entries.

As such, the space complexity of the algorithm is O(m * n) due to the memoization storage, with an additional consideration for the recursive call stack depth.

In the given code, the d variable is also a memoization cache, but its entries are only based on the available prices, so it doesn't affect the overall worst-case space complexity, which is still O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄