LeetCode 2312. 卖木头块

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;
        //整块不分开
        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) {
    	// 二维表存储价格
        for(auto&& p : prices)
            price[p[0]][p[1]] = p[2];
        return dfs(n, m);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

记忆化搜索 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];
        //整块不分开
        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) {
    	// 二维记录价格
        for(auto&& p : prices)
            price[p[0]][p[1]] = p[2];
        memset(f, -1, sizeof f);
        return dfs(n, m);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

优雅动态规划

const int N = 210;
typedef long long LL;
class Solution {
public:
    LL f[N][N] = {0}; //表示i行j列的方块最大值
    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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25