2024.03.15

2312.卖木头块

https://leetcode.cn/problems/selling-pieces-of-wood/

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

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

沿垂直方向按高度 完全 切割木块，或
沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。

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

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

提示：

1 <= m, n <= 200
1 <= prices.length <= 2 * 104
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 106
所有 (hi, wi) 互不相同 。

&emsp;01背包问题plus。
&emsp;虽然看到题目的第一眼就知道是用动态规划，但是在思考状态转移方程的时候思维僵化了，固执地认为dp[i][j]的值一定要通过dp[i][j-1]的值计算。看了提示以后发现，不应该从木块大小的角度思考问题，应该从木块切割方式的角度来思考。
&emsp;换句话说即是从木块拼接方式的角度来思考。
&emsp;对于一块m*n的木块，其可以直接整块卖出，或者切割一次，卖出比如说大小为m1*n和m2*n的两块木块，价格取最大者即可，而小木块又可以继续像这样再分割。
&emsp;因此动态规划的状态转移方程应该是，对位置m,n，取其单独卖出和切割一次卖出的最大价格，而切割一次卖出的最大价格即是遍历切割方式，取价格最高的两个小块的和。
&emsp;不过官方题解里面用的哈希我这里省略掉了。

&emsp;代码：（java）

class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        long[][] dp = new long[m][n];
        for(int i=0;i<prices.length;i++){
            int m_ = prices[i][0];
            int n_ = prices[i][1];
            int pr = prices[i][2];
            dp[m_-1][n_-1] = pr;
        } // 为dp数组赋初始值，即初始价格
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j] = Math.max(calculate_m_n_price(i,j,dp), dp[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
    private long calculate_m_n_price(int m, int n, long[][] dp){
        // 先按列切割，即竖着切
        int a=0;
        int b=n-1;
        long max_price = 0;
        while(a<=b){
            long temp_price = dp[m][a] + dp[m][b];
            max_price = Math.max(max_price, temp_price);
            a+=1;
            b-=1;
        }
        // 然后按行切割，即横着切
        a=0;
        b=m-1;
        while(a<=b){
            long temp_price = dp[a][n] + dp[b][n];
            max_price = Math.max(max_price, temp_price);
            a+=1;
            b-=1;

        }
        return max_price;
    }
}

&emsp;时间复杂度：O(mn(m+n)+p)，其中 p 是数组 prices 的长度。
&emsp;空间复杂度：O(mn)，即为动态规划的数组需要使用的空间。