给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
使用动态规划解法，三个步骤：
- 定义状态， dp[i] [j]为第i行，包含第j列的最小三角形路径和。
- 定义初始值，假设我们dp数组从1 1开始取值，则dp[0] [0] = 0; dp[1] [1]就是 三角形[0] [0],也就是三角形的顶部。
- 定义动态转移方程，
- dp[i] [j] 当 j 是第一列时，则为dp[i - 1] [j] + 三角形[i] [j].
- 当 j 为最后一列时, 则dp[i] [j] 为dp[i - 1] [j - 1].
- 当j 不是第一列也不是最后一列时， dp[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
31
32
33
34
35
36
37
|
public static int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) return 0;
if (triangle.size() == 1) return triangle.get(0).get(0);
// 定义状态 dp[i][j] 代表到第 i 行，第 j 列 的最小路径和
int[][] dp = new int[triangle.size() + 1][triangle.get(triangle.size() - 1).size() + 1];
// 初始值
dp[0][0] = 0;
dp[1][1] = triangle.get(0).get(0);
// 状态转移方程
int result = Integer.MAX_VALUE;
for (int i = 2; i <= triangle.size(); i++) {
List <Integer> list = triangle.get(i - 1);
for (int j = 1; j <= list.size(); j++) {
if (j == 1){
// 最左
dp[i][j] = dp[i - 1][1] + list.get(0);
}else if (j == list.size()){
// 最右
dp[i][j] = dp[i-1][j-1] + list.get(j - 1);
}else {
// 中间
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + list.get(j - 1);
}
if (i == triangle.size()) {
result = Math.min(result,dp[i][j]);
}
}
}
return result;
}
|
时间复杂度 : O(N)
空间复杂度 : O(M * N) 因为用到了额外的二维数组存储元素。 M N分别为三角形的行数和列数。
优化：
上述算法中，我们用到了二维数组， 用来存储矩阵各个点的最小路径， 通过观察发现， 我们计算dp[i] [j] 时，好像只用到了dp[i - 1] […]中的数值，是否可以将空间复杂度由之前的 M * N优化至 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
25
26
27
28
29
30
31
32
33
34
|
public static int minimumTotal(List<List<Integer>> triangle) {
// 定义状态 dp[i] 代表当前行，第 i 列 的最小路径和
int[] dp = new int[triangle.size()];
// 初始值
dp[0] = 0;
dp[1] = triangle.get(0).get(0);
// 状态转移方程
int result = Integer.MAX_VALUE;
for (int i = 2; i <= triangle.size(); i++) {
List <Integer> list = triangle.get(i - 1);
for (int j = list.size(); j > 0; j--) {
if (j == 1){
// 最左
dp[j] = dp[1] + list.get(0);
}else if (j == list.size()){
// 最右
dp[j] = dp[j-1] + list.get(j - 1);
}else {
// 中间
dp[j] = Math.min(dp[j-1], dp[j]) + list.get(j - 1);
}
if (i == triangle.size()) {
result = Math.min(result,dp[j]);
}
}
}
return result;
}
|
做此优化时 ，内部的遍历需要从后往前遍历，因为从前往后，争取的值会被覆盖掉，如下图：
最终计算出来的结果是15，导致不正确。
所以需要从后往前遍历，正确的值不会被覆盖掉，如下图：
值不会被覆盖，可以得到争取的值 11.
算法时间复杂度仍然是 : O(N)
空间复杂度由之前的O(N * M) 降低为 O(N).