LeetCode 2312. Sell Wood Blocks

LeetCode 2312. 卖木头块

暴力递归 TLE

const int N = 210;
typedef long long LL;
class Solution {
    
public:
    int price[N][N] = {
    0};
    LL dfs(int n, int m)
    {
    
        if(n == 0 || m == 0)
            return 0;
        //The whole piece is not separated
        LL p1 = price[n][m];
        // 按行分
        LL p2 = 0;
        for(int i = 1; i < n; i ++)
        {
    
            LL up = dfs(i, m);
            LL down = dfs(n - i, m);
            p2 = max(p2, up + down);
        }
        // 按列分
        LL p3 = 0;
        for(int i = 1; i < m; i ++)
        {
    
            LL left = dfs(n, i);
            LL right = dfs(n, m - i);
            p3 = max(p3, left + right);
        }
        return max(p1, max(p2, p3));
    }
    long long sellingWood(int n, int m, vector<vector<int>>& prices) {
    
    	// A two-dimensional table stores prices
        for(auto&& p : prices)
            price[p[0]][p[1]] = p[2];
        return dfs(n, m);
    }
};

记忆化搜索 AC

const int N = 210;
typedef long long LL;
class Solution {
    
public:
    int price[N][N] = {
    0};
    LL f[N][N];
    LL dfs(int n, int m)
    {
    
        // 0行或者0列
        if(n == 0 || m == 0)
            return 0;
        // 记忆化
        if(f[n][m] != -1) 
            return f[n][m];
        //The whole piece is not separated
        LL p1 = price[n][m];
        // 按行分
        LL p2 = 0;
        for(int i = 1; i < n; i ++)
        {
    
            LL up = dfs(i, m);
            LL down = dfs(n - i, m);
            p2 = max(p2, up + down);
        }
        // 按列分
        LL p3 = 0;
        for(int i = 1; i < m; i ++)
        {
    
            LL left = dfs(n, i);
            LL right = dfs(n, m - i);
            p3 = max(p3, left + right);
        }
        f[n][m] = max(p1, max(p2, p3));
        return f[n][m];
    }
    long long sellingWood(int n, int m, vector<vector<int>>& prices) {
    
    	// 2D record price
        for(auto&& p : prices)
            price[p[0]][p[1]] = p[2];
        memset(f, -1, sizeof f);
        return dfs(n, m);
    }
};

Elegant dynamic programming

const int N = 210;
typedef long long LL;
class Solution {
    
public:
    LL f[N][N] = {
    0}; //表示i行jThe maximum block size of the column
    long long sellingWood(int n, int m, vector<vector<int>>& prices) {
    
    	// 初始化
        for(auto&& p : prices)
            f[p[0]][p[1]] = p[2];
        
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
    
                // 按行分割
                for(int k = 1; k <= (i >> 1); k ++)
                    f[i][j] = max(f[i][j], f[k][j] + f[i - k][j]);

                // 按列分割
                for(int k = 1; k <= (j >> 1); k ++)
                    f[i][j] = max(f[i][j], f[i][k] + f[i][j - k]);
                
            }
        return f[n][m];
    }
};