LC.P2312[卖木头块]

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        int[][] pr = new int[m + 1][n + 1];
        for (int[] p : prices) {
            pr[p[0]][p[1]] = p[2];
        }
        long[][] f = new long[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <=n; ++j) {
                f[i][j] = pr[i][j];
                // 垂直切割
                for (int k = 1; k < j; ++k) f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);
                // 水平切割
                for (int k = 1; k < i; ++k) f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);
            }
        }
        return f[m][n];
    }
}
  • 时间复杂度：$O(mn(m + n))$
  • 空间复杂度：$O(mn)$

方法二：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long sellingWood(int m, int n, int[][] prices) {
        long[][] f = new long[m + 1][n + 1];
        for (int[] p : prices) {
            f[p[0]][p[1]] = p[2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 垂直切割
                for (int k = 1; k <= j / 2; k++) f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);
                // 水平切割
                for (int k = 1; k <= i / 2; k++) f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);
            }
        }
        return f[m][n];
    }
}
  • 时间复杂度：$O(mn(m + n))$
  • 空间复杂度：$O(mn)$