leetcode2312. 卖木头块（困难，周赛）

思路：dp
如何想到dp的？
垂直/水平切割，得到更小的子问题
先垂直再水平和先水平再垂直会得到同样大小的两块木块，因此1：存在重复子问题
对于同样高和宽的两个木块所获得的最多钱数和得到这两个木块的过程无关，因此2：无后效性
获得两块小木块的最多钱数，就获得了大木块的最多钱数，因此3：最优子结构
满足以上三个条件，因此->dp
状态转移：
p[m][n]表示高m宽n的木块能获得的最大钱数
dp[m][n]能直接卖的话获得一个price
dp[m][n]=max(dp[m][j]+dp[m][n-j]),1<=j<=n-1
dp[m][n]=max(dp[j][n]+dp[m-j][n]),1<=j<=m-1
递归终止：dp[1][1]
代码实现方式？由于会遍历到所有的状态，因此用递推实现

class Solution {
    
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
    
 
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1)); //long long
        auto p = dp;
        for (auto& a : prices) p[a[0]][a[1]] = a[2];
        for (int i = 1; i <= m; ++i) {
    
            for (int j = 1; j <= n; ++j) {
    
                dp[i][j] = p[i][j];
                for (int k = 1; k <= j - 1; ++k) dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
                for (int k = 1; k <= i - 1; ++k) dp[i][j] = max(dp[i][j], dp[k][j] + dp[i-k][j]); 
            }
        }
        return dp[m][n];
    }
};