LeetCode题解-120. 三角形最小路径和

发表于 分类于

题目描述

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

例如，给定三角形：

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 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路

标准的一道动态规划。假设三角形数组为使用dp[i][j]表示自顶向下到第i行第j列的最小路径，容易得到状态转移方程：

i行1列的状态只能由i-1行1列转移而来，即

1
dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);

i行最后一列的状态只能由i-1行最后一列转移而来，即

1
dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);

其他状态可由左上和右上转移而来，即

1
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j)

边界值

1
dp[0][0] = triangle.get(0).get(0)

初步代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[][] dp = new int[n][n];
    dp[0][0] = triangle.get(0).get(0);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < triangle.get(i).size(); j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
            } else if (j == triangle.get(i).size() - 1) {
                dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; ++i) {
        ans = Math.min(dp[n - 1][i], ans);
    }
    return ans;
}

优化代码

通过上述代码可以发现，dp[i][j]只跟dp[i - 1][j - 1]和dp[i - 1][j]有关，因此可另dp[i - 1][j - 1]为pre，dp[i - 1][j]为cur，这样就把二维数组降为一为数组，空间复杂度也从O(n2)降为O(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
public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        int pre = 0, cur;
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                cur = dp[j];
                if (j == 0) {
                    dp[j] = cur + triangle.get(i).get(j);
                } else if (j == triangle.get(i).size() - 1) {
                    dp[j] = pre + triangle.get(i).get(j);
                } else {
                    dp[j] = Math.min(cur, pre) + triangle.get(i).get(j);
                }
                pre = cur;
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            ans = Math.min(dp[i], ans);
        }
        return ans;
    }