120.三角形最短路径和
题目
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）
方法1（暴力递归）
设f(i,j)为从位置(i,j)到最后一行的最短路径和。则可以发现如下规律：
$$f(i,j) = min(f(i+1,j) , f(i+1,j+1)) + triangle[i][j]$$
根据上述规律，很容易就可以写出以下暴力递归的方法。
1
2
3
4
5
6
7
8
| public int minimumTotal(List<List<Integer>> triangle) {
return help(triangle, 0, 0);
}
public int help(List<List<Integer>> triangle, int i, int j){
if(i = triangle.size())
return 0;
return Math.min(help(triangle, i + 1, j), help(triangle, i + 1, j + 1)) + triangle.get(i).get(j));
}
|
暴力递归的方法会产生很多重复计算，因此动态规划方法要用额外的dp数组来进行优化。
方法2（动态规划）
对暴力递归方法进行分析可以知道，用来确定返回值状态的可变参数为i和j，也即位置。
因此定义二维的dp数组。其中dp[i][j]的含义为：从(i, j)位置走到三角形最后一行的最短路径和。
状态转移方程为：
$$dp(i,j) = min(dp(i+1,j) , dp(i+1,j+1)) + triangle[i][j]$$
由三角形的最后一行不断向上进行状态转移。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++){
dp[n - 1][i] = triangle.get(n - 1).get(i);
}
for(int i = n - 2; i >= 0; i--){
for(int j = 0; j <= i; j++)
dp[i][j] = Math.min(dp[i+1][j] , dp[i+1][j+1]) + triangle.get(i).get(j);
}
return dp[0][0];
}
|
时间复杂度：O(n^2)
空间复杂度：O(n^2)
方法3（对空间进行优化）
对方法2的实际运行过程进行分析，可以发现。对于dp[i][j]的计算，只需要知道dp数组第i+1行的情况即可，因此无需将整个dp数组的N行全部保存，只保存第i+1行这一行就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
| public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n];
for(int j = 0; j < n; j++)
dp[j] = triangle.get(n - 1).get(j);
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
|
时间复杂度：O(n^2)
空间复杂度：O(n)