echo

任生命穿梭 时间的角落

0%

三角形最小路径和

Posted on Edited on In Valine:

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

我们使用 f[i][j]来表示从三角形顶部走到位置(i, j)的最小路径和。这里的 i 和 j 指的是三角形中第i行第j列（从 0 开始编号）的的位置。

由于每一步只能移动到下一个相邻的结点，要到位置(i, j)，上一步位置就只能在(i - 1, j)或(i - 1, j - 1)中选择。我们在两者之间找一个路径和比较小的来转移，状态方程为：
$$
f[i][j] = min(f[i -1][j - 1], f[i - 1][j]) + c[i][j]
$$
其中c[i][j]表示位置(i, j)对应的元素值。

注意边界条件：

  • 当 j == 0 时，没有左上结点，只能从上一个结点转移过来，状态转移方程为：
    $$
    f[i][j] = f[i - 1][j] + c[i][j]
    $$

  • 当 j == i 时，没有上结点，只能从左上结点转移过来，状态转移方程为：

$$
f[i][j] = f[i - 1][j - 1] + c[i][j]
$$

最终的答案为 f[n - 1][0] 到 f[n - 1][n - 1] 的最小值，其中 n 是三角形的行数。

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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if(m == 0){
            return 0;
        }
        int n = triangle.get(m - 1).size();

        int[][] dp = new int[m][n];
        dp[0][0] = triangle.get(0).get(0);

        for(int i = 1; i < m; i++){
            for(int j = 0; j < i + 1; j++){
                int up = j != i ? dp[i - 1][j] : Integer.MAX_VALUE;
                int upLeft = j - 1 >= 0 ? dp[i - 1][j - 1] : Integer.MAX_VALUE;

                dp[i][j] = triangle.get(i).get(j) + Math.min(up, upLeft); 
            }
        }

        int min = dp[m - 1][0];
        for(int i = 1; i < n; i++){
            min = Math.min(min, dp[m - 1][i]);
        }
        return min;
    }
}

时间复杂度O(n^2)，空间复杂度O(n^2)。

我们可以看到 dp 数组中第 i 行的值只与第 i - 1 行的值有关，我们可以只使用一个一维数组存储。

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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if(m == 0){
            return 0;
        }
        int n = triangle.get(m - 1).size();

        int[] dp = new int[n];
        dp[0]= triangle.get(0).get(0);
        int up = 0, upLeft = 0;
        for(int i = 1; i < m; i++){
            for(int j = 0; j < i + 1; j++){
                up = dp[j];
                if(j == 0){
                    dp[j] = up + triangle.get(i).get(j);
                }else if(j == i){
                    dp[j] = upLeft + triangle.get(i).get(j);
                }else{
                    dp[j] = Math.min(up, upLeft) + triangle.get(i).get(j);
                }
                //第 j + 1 个元素的左上元素等于第 j 个元素上方的元素
                upLeft = up;
            }
        }

        int min = dp[0];
        for(int i = 1; i < n; i++){
            min = Math.min(min, dp[i]);
        }
        return min;
    }
}

时间复杂度O(n^2)，空间复杂度O(n)。