feat: $5224

robot · robot · commit 2a4dc37ef459 · 2022-06-19T14:59:11.000+08:00
diff --git a/README.md b/README.md
@@ -538,6 +538,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [2209. 用地毯覆盖后的最少白色砖块](./problems/2209.minimum-white-tiles-after-covering-with-carpets.md) 👍
 - [2281. 巫师的总力量和](./problems/2281.sum-of-total-strength-of-wizards.md)
 - [2306. 公司命名](./problems/2306.naming-a-company.md) 枚举优化好题
+- [5254. 卖木头块](./problems/5254.selling-pieces-of-wood.md) 动态规划经典题
 - [5999. 统计数组中好三元组数目](./problems/5999.count-good-triplets-in-an-array.md) 👍
 
 ## :trident: &nbsp;anki 卡片
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -353,6 +353,7 @@
   - [2209. 用地毯覆盖后的最少白色砖块](./problems/2209.minimum-white-tiles-after-covering-with-carpets.md)
   - [2281.sum-of-total-strength-of-wizards](./problems/2281.sum-of-total-strength-of-wizards.md)
   - [2306. 公司命名](./problems/2306.naming-a-company.md) 枚举优化好题
+  - [5254. 卖木头块](./problems/5254.selling-pieces-of-wood.md) 动态规划经典题
   - [5999. 统计数组中好三元组数目](./problems/5999.count-good-triplets-in-an-array.md) 👍
 
 - [后序](epilogue.md)
diff --git a/problems/5254.selling-pieces-of-wood.md b/problems/5254.selling-pieces-of-wood.md
@@ -0,0 +1,131 @@
+## 题目地址(5254. 卖木头块)
+
+https://leetcode.cn/problems/selling-pieces-of-wood/
+
+## 题目描述
+
+```
+给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
+
+每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
+
+沿垂直方向按高度 完全 切割木块，或
+沿水平方向按宽度 完全 切割木块
+
+在将一块木块切成若干小木块后，你可以根据 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 * 104
+prices[i].length == 3
+1 <= hi <= m
+1 <= wi <= n
+1 <= pricei <= 106
+所有 (hi, wi) 互不相同 。
+```
+
+## 前置知识
+
+- 动态规划记忆化递归
+
+## 公司
+
+- 暂无
+
+## 思路
+
+这是一个经典的枚举割点的动态规划问题。
+
+相关题目有铺地毯/瓷砖，本质都是给你一个二维矩阵，给你一堆价值，让你求如何分割价值最小或最大。
+
+可以这么做的前提是如果我们可以切割，那么切割后会变为两个子矩阵，这两个子矩阵和切割前除了大小不一样，其他都一样。因此可以不断枚举割点，递归解决。
+
+定义 dp[i][j] 为切割长度为 i 宽度为 j 的木板的最大价格，那么答案就是 dp[m,n]
+
+接下来，我们枚举横着切的切点和竖着切的切点就可以得到答案。
+
+切割前我们有三种选择：
+
+1. 横着切，切哪呢？枚举所有可能。因为横着切本质是高度变了，宽度不变，因此枚举所有可能就是枚举高度为 [1,i-1]（其中 i 为当前木板高度）
+2. 竖着切，同理
+3. 不切。
+
+取三种情况的最大值即可。
+
+## 关键点
+
+- 枚举切割点
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+class Solution:
+    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
+        d = {(h, w): p for h, w, p in prices}
+        @cache
+        def dp(i, j):
+            ans = d.get((i, j), 0) # 不切
+            # 竖着切
+            for x in range(1, i):
+                ans = max(ans, dp(x, j) + dp(i - x, j))
+            # 横着切
+            for y in range(1, j):
+                ans = max(ans, dp(i, y) + dp(i, j - y))
+            return ans # 且三种选择的最大值即可
+        return dp(m, n)
+
+```
+
+**复杂度分析**
+
+令 t 为 prices 长度。
+
+- 时间复杂度：$O(n * m * (n + m))$
+- 空间复杂度：$O(t + n * m)$
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
