leetcode2312. Selling wood blocks (difficult, weekly race)

Ideas ：dp
How to think of dp Of ？
vertical / Cut horizontally , obtain Smaller subproblems
First vertical then horizontal and first horizontal then vertical will Get two pieces of wood of the same size , therefore 1： There are duplicate subproblems
For the same height and width The maximum amount of money obtained from two blocks has nothing to do with the process of obtaining these two blocks , therefore 2： No aftereffect
get The maximum amount of money for two small wooden blocks , You get the maximum amount of money for large wooden blocks , therefore 3： Optimal substructure
Meet the above three conditions , therefore ->dp
State shift ：
p[m][n] Express high m wide n The maximum amount of money you can get from a piece of wood
dp[m][n] You can get one if you can sell it directly 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
Recursive termination ：dp[1][1]
Code implementation ？ Because it will traverse all States , Therefore, it is realized by recursion

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];
    }
};