#2312

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Selling Pieces of Wood

Maximize your profit by cutting a wooden piece into smaller parts based on given prices and dimensions.

Problem Statement

You are given the dimensions of a rectangular piece of wood with height m and width n, along with a list of prices for smaller rectangular pieces. Each price entry consists of height hi, width wi, and the price pricei you can earn by selling a piece with those dimensions. You can make cuts along the wood's height or width to split it into smaller pieces, and you can sell multiple pieces of the same shape. The task is to determine the maximum amount of money you can earn after making cuts.

Note that the wood's grain matters, so you cannot rotate pieces to swap height and width. For each cut, you can either split the wood vertically or horizontally. You can use memoization and dynamic programming to keep track of the best possible profits for all valid subproblems and transitions between them.

Examples

Example 1

Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]

Output: 19

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

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 Approach

Dynamic Programming Approach

This problem can be efficiently solved using dynamic programming, where you maintain a table to store the maximum profit for every subproblem defined by the height and width of the wood. The state transition involves considering both vertical and horizontal cuts for all dimensions from 1 x 1 to m x n, updating the maximum profit recursively based on previously computed values.

Memoization for Optimization

Memoization helps in storing the results of subproblems, ensuring that each subproblem is solved only once. This prevents redundant calculations, significantly optimizing the algorithm. For each dimension of the wood, memoization ensures that overlapping subproblems are handled efficiently.

Iterative Approach to Maximize Profit

Iterate through all possible cuts and dimensions to check all possibilities. For each cut, compare the profit made by splitting the wood into smaller pieces versus not cutting it. The maximum profit is the result of considering both the cut and non-cut cases at each step.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the dynamic programming approach, where you have to iterate through all possible subproblems. The space complexity is also tied to the dimensions of the dynamic programming table. In the worst case, the time complexity is O(m * n * (m + n)), and the space complexity is O(m * n).

What Interviewers Usually Probe

Ability to efficiently solve dynamic programming problems with state transitions.
Understanding of memoization and how it optimizes recursive subproblem solutions.
Proficiency in iterating through all possible subproblems to determine optimal solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to consider both vertical and horizontal cuts at each step.
Not using memoization, which leads to redundant calculations and increased time complexity.
Overlooking the fact that you cannot rotate the wood pieces, which could affect the available dimensions.

Follow-up variants

Problem with larger dimensions and increased number of price entries.
Variation with added constraints on how many times each piece can be sold.
Adjusted problem where you need to minimize the total number of cuts.

FAQ

How do I approach the 'Selling Pieces of Wood' problem?

The problem can be tackled using dynamic programming and memoization to keep track of the best possible profit for each subproblem based on all possible cuts.

What is the optimal time complexity for solving this problem?

The optimal time complexity is O(m * n * (m + n)), where m and n represent the dimensions of the wood. This is due to the need to evaluate all possible subproblems and state transitions.

What is memoization, and why is it crucial here?

Memoization is a technique that stores the results of expensive subproblems, avoiding redundant computations. It significantly speeds up the solution by caching previously computed values.

Can I rotate the pieces to change their dimensions?

No, the problem specifies that the grain of the wood matters, and thus you cannot rotate the pieces to swap their height and width.

How does GhostInterview help with dynamic programming problems?

GhostInterview provides an interactive solver that walks you through dynamic programming approaches, ensuring you understand the state transitions and memoization techniques to solve problems efficiently.

terminal

Solution

Solution 1: Memoization Search

First, we define a 2D array $d$, where $d[i][j]$ represents the price of a wood block with height $i$ and width $j$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        @cache
        def dfs(h: int, w: int) -> int:
            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)

Solution 2: Dynamic Programming

We can transform the memoization search in Solution 1 into dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        @cache
        def dfs(h: int, w: int) -> int:
            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)

Continue Practicing

#2328 number of increasing paths in a grid #2019 the score of students solving math expression #2713 maximum strictly increasing cells in a matrix