# 2312. 卖木头块

### 题目地址(2312. 卖木头块)

<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://p.ipic.vip/m9itjv.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2312.selling-pieces-of-wood.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.