leetcode 2312. 卖木头块【划分型dp+棋盘切割类型dp】

原题链接：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) 互不相同 。

解题思路：

这个题目是一个经典的棋盘切割dp，严格来说其实也算一个划分类型dp，这个题目要注意的就是每次切割都是完全切割的，不存在那种切到一半再转方向的那种切割，如果不是完全切割切到一半可以转方向那种，我感觉这个题目就难多了，但是这个题目说了是完全切割，一刀直接切到底的那种，这样就简单多了，这个时候属于经典的棋盘切割dp,直接考虑dp即可。

如下图所示图1属于完全切割类型，就可以考虑进行dp，图2属于不完全切割，就不好处理了，这个题目属于图1这种情况可以直接考虑dp

dp处理过程如下

状态定义：

f[i][j]表示高为i，宽为j的矩形通过切割能获得的最大钱数。

初始化：

宽为0或者高为0时矩形的收益都是0

状态转移：

对于当前矩形有三种情况

(1)直接卖掉当前矩形

(2)考虑水平切割，枚举切割位置

f[i][j]=max(f[i][j],f[k][j]+f[i-k][j]);  (1<=k<i),要分为俩部分，所以每一边的高至多为i-1,

(3)考虑垂直切割，枚举切割位置

f[i][j]=max(f[i][j],f[i][k]+f[i][j-k]);  (1<=k<j),要分为俩部分，所以每一边的宽至多为j-1

最终答案：

最终答案就是将高为m，宽为n的矩形进行切割能获取的最大钱数，答案就是f[m][n]。

时间复杂度：O(m*n*(m+n))，枚举高O(m),枚举宽O(n),枚举切割位置O(n+m)。

空间复杂度：O(m*n+len(prices),dp使用的f数组为O(m*n)，哈希表存储所有的prices中的数据O(len(prices))。

cpp代码如下：

class Solution {
    typedef long long LL;
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<LL>>f(m+1,vector<LL>(n+1));
        map<pair<int,int>,int>mp;
        for(auto& t:prices){
            mp[pair{t[0],t[1]}]=t[2];
        }

        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                //直接卖掉
                if(mp.count({i,j})){
                    f[i][j]=mp[{i,j}];
                }

                //水平切割
                for(int k=1;k<i;k++)
                    f[i][j]=max(f[i][j],f[k][j]+f[i-k][j]);

                //垂直切割
                for(int k=1;k<j;k++)
                    f[i][j]=max(f[i][j],f[i][k]+f[i][j-k]);
            }

        return f[m][n];
    }
};