题目
给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
沿垂直方向按高度 完全 切割木块，或
沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。
请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。
注意你可以切割木块任意次。
示例
输入：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 元是最多能得到的钱数。‘
输入：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.状态定义 ： dp[i][j]表示卖掉高度为i，宽度为j的木块能够获得的最大收益。在这个定义下，dp[m][n]就是最终答案。
2.先根据prices数组，初始化一些dp状态，如果存在同一尺寸的木块，保留最大价值。然后分横着切合竖着切两种情况，枚举切割点。
（1）假设横着切，且切割后上面木块的高度为k，则下面木块的高度就是i−k，状态转移方程为dp[i][j]=max（dp[i][j],dp[k][j]+dp[i−k][j]）。
（2）假设竖着切，且切割后左边木块的宽度为k，则右边木块的宽度就是j−k，状态转移方程为dp[i][j]=max（dp[i][j],dp[i][k]+dp[i][j−k])。
代码
using LL = long long;
const int N = 210;
LL dp[N][N];
class Solution {
public:
long long sellingWood(int m, int n, vector<vector<int>>& prices) {
memset(dp,0,sizeof(dp));
for(auto &price : prices)
{
//h为高 w为宽
int h = price[0],w = price[1];
//dp[h][w]代表当高为h宽为w的最大价值
//此处是对dp数组的初始化
dp[h][w] = max(dp[h][w],(LL)price[2]);
}
for(int i = 1;i <= m ;i++)
{
for(int j = 1;j <= n;j++)
{
//横着切
for(int k = 0;k <= i;k++)
{
dp[i][j] = max(dp[i][j],dp[k][j] + dp[i-k][j]);
}
for(int k = 0;k <= j;k++)
{
dp[i][j] = max(dp[i][j],dp[i][k] + dp[i][j - k]);
}
}
}
return dp[m][n];
}
};