leetcode解题: Triangle (120)

发表于 | 分类于

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解法1：DP O(N^2) with O(N^2) 空间

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
public int minimumTotal(List(List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }
    
    int n = triangle.size();    // number of rows
    
    int[][] dp = new int[n][n];
    
    for (int[] temp : dp) {
        Arrays.fill(temp, Integer.MAX_VALUE);
    }
    
    dp[0][0] = triangle.get(0).get(0);
    
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        for (int j = 1; j <=i; j++) {
            dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
        }
    }
    
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.min(res, dp[n - 1][i]);
    }
    
    return res;
}

解法2：DP O(N^2) with O(N) 空间

观察上面的解法可以看到，我们的2维数组实际上只用到了上一行的信息，由此我们可以对内存做一个小优化而达到O(N)的空间。
我们只保留上一行的每一个位置的最小值，需要一个大小为N的数组，N是总的行数，然后在计算中只要反复更新这个数组。
也就是说dp[i] = Math.min(dp[i - 1], dp[i]) + A[j][i] j是现在计算到的行数

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
public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }
    
    int n = triangle.size();    // number of rows
    
    int[] dp = new int[n];
    
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = triangle.get(0).get(0);
    
    for (int i = 1; i < n; i++) {
        // i is the current row number
        for (int j = i; j >= 0; j--) {
            // 这里比较容易出错，j要从后往前更新，因为下一行的计算用到了上一行的[i - 1] 和[i]，
            // 需要先更新后面的才不会override前面的数据
            // 同时下标使用的是j以此来模拟不同column的计算
            dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
        }
    }
    
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.min(res, dp[i]);
    }
    
    return res;
}