2312. 卖木头块 - 《算法》

题目
思路
代码

题目

给你两个整数 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 * 10^4
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 10^6
所有 (hi, wi) 互不相同。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/selling-pieces-of-wood
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

比赛时一打眼感觉很难，看没多少人做出来，就没细想，结果一看正解好像也没那么难，害，不能轻易放弃啊，一次AK的机会没把握住。

dp状态的定义很直接， $2312. 卖木头块 - 图3$ 表示高为i、宽为j的木头块可以卖的最多钱数。

枚举对这块木头可以进行的操作：

不切割
横向切割，分别在第一行、第二行、…、倒数第二行下面切
纵向切割，分别在第一列、第二列、…、倒数第二列右面切

$2312. 卖木头块 - 图4$ 变可以从上面三大类情况转移过来。

进一步可以发现，从第一行和倒数第二行处切的结果是一样的，因此枚举的切割位置可以减半。

代码

class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        long[][] dp = new long[m + 1][n + 1];
        for (int[] arr : prices) {
            // 对于高arr[0]、宽arr[1]的木块，不切割可以卖出arr[2]钱数
            dp[arr[0]][arr[1]] = arr[2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 横向切割，枚举切出的较小木块的高，只需枚举到i/2
                for (int k = 0; k <= i / 2; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
                // 纵向切割，枚举切出的较小木块的宽，只需枚举到j/2
                for (int k = 0; k <= j / 2; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
            }
        }
        return dp[m][n];
    }
}