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.

#2312

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

卖木头块

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [h i , w i , price i ] 表示你可以以 price i 元的价格卖一块高为 h i 宽为 w i 的矩形木块。每一次操作中，你必须按下述方式之一执行…

数组动态规划记忆化

题目描述

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [h_i, w_i, price_i] 表示你可以以 price_i 元的价格卖一块高为 h_i 宽为 w_i 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

沿垂直方向按高度完全切割木块，或
沿水平方向按宽度完全切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你不能旋转切好后木块来交换它的高度值和宽度值。

请你返回切割一块大小为 m x n 的木块后，能得到的最多钱数。

注意你可以切割木块任意次。

示例 1：

输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。

示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

提示：

1 <= m, n <= 200
1 <= prices.length <= 2 * 10⁴
prices[i].length == 3
1 <= h_i <= m
1 <= w_i <= n
1 <= price_i <= 10⁶
所有 (h_i, w_i) 互不相同 。

lightbulb

解题思路

方法一：记忆化搜索

我们先定义一个二维数组 $d$ ，其中 $d[i][j]$ 表示高为 $i$ ，宽为 $j$ 的木块的价格。初始时，我们遍历价格数组 $prices$ ，将每一块木块 $(h, w, p)$ 的价格 $p$ 存入 $d[h][w]$ 中，其余价格为 $0$ 。

然后我们设计一个函数 $dfs(h, w)$ ，表示对一块高为 $h$ ，宽为 $w$ 的木块切割后能得到的最多钱数。答案就是 $dfs(m, n)$ 。

函数 $dfs(h, w)$ 的执行过程如下：

如果 $(h, w)$ 已经被计算过了，直接返回答案。
否则，我们先初始化答案为 $d[h][w]$ ，然后枚举切割的位置，分别计算切割后的两块木块能得到的最多钱数，取最大值即可。

时间复杂度 $(m \times n \times (m + n) + p)$ ，空间复杂度 $O(m \times n)$ 。其中 $p$ 表示价格数组的长度，而 $m$ 和 $n$ 分别表示木块的高和宽。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2328 网格图中递增路径的数目 #2019 解出数学表达式的学生分数 #2713 矩阵中严格递增的单元格数