🔽 120.三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 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
| class Solution {
//回溯法就能找到最终的结果
int res=Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp=new int[triangle.size()];
backtrack(triangle,0,0,0);
return res;
}
private void backtrack(List<List<Integer>> triangle,int index,int sum,int pos){
//到达最后一层就可以尝试更新结果
if(index==triangle.size()){
res=Math.min(res,sum);
return;
}
//没有到达最后一层，那么就从当前层开始回溯找到每一种组合
for(int i=0;i<triangle.get(index).size();++i){
//下一层的节点与上层节点相邻才能统计
if(i==pos||i==pos+1){
int num=triangle.get(index).get(i);
backtrack(triangle,index+1,sum+num,i);
}
}
}
}
|
这种方法超时！！！
最开始理解的是每一行都选择一个最小的数，最后就可以得到最终的结果，但是事实上并不是这样，例如对于{{-1},{2,3},{1,-1,-3}}来说，最好的结果是选择{-1,3,-3}得到结果-1，而不是选择每一行中最小的{-1,2,-1}得到结果0，原因就是因为当前行选择了最小的，由于下标限制，下一行中就可能不能选择最小的，所以要利用动态规划列举出所有符合要求的结果，然后在最后一行中找到最终的结果
对于当前位置{i,j}来说，形成的最小值与上一行的{i-1,j}和{i-1,j-1}有关，并且对于边界来说，左边界{i,0}只与{i-1,0}有关，右边界{i,j}只与{i-1,j-1}有关，为了统一dp数组的更新，我们给dp数组增加一列，并且将其初始化为最大值，这样边界也可以当成普通位置处理，最终的dp数组更新公式为：
$$
dp[i][j+1]=Math.min(dp[i-1][j+1],dp[i-1][j])+nums[i][j]
$$
更新完dp数组之后，只需要在最后一行挑选出一个最小值就得到了三角形的最小路径和
执行流程
- 初始化dp数组，多一列，初始化全为
Integer.MAX_VALUE - 从第一列开始遍历，第零列直接选择唯一的元素即可
- 每一个元素按照更新公式更新即可
- 更新完毕从最后一行中找出一个最小值就是最终的结果
代码
根据以上分析得出以下代码：
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
| class Solution {
//回溯法就能找到最终的结果，思路很简单，但是会超时
//当前位置的值等于上层中两个值的最小值，在最后一层中选择最小的值
public int minimumTotal(List<List<Integer>> triangle) {
//下标从[0][1]开始，这样初始和结束可以不看成边界
//相当于第一列未标记，新增了这一列
int[][] dp=new int[triangle.size()][triangle.get(triangle.size()-1).size()+1];
int res=Integer.MAX_VALUE;
for(int i=0;i<dp.length;++i){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
dp[0][1]=triangle.get(0).get(0);
for(int i=1;i<triangle.size();++i){
List<Integer> row=triangle.get(i);
for(int j=0;j<row.size();++j){
//当前位置的dp值和上一层的相邻两个节点有关
dp[i][j+1]=Math.min(dp[i-1][j+1],dp[i-1][j])+row.get(j);
}
}
//从最后一行中找出最终的答案
for(int i=1;i<dp[dp.length-1].length;++i){
res=Math.min(res,dp[dp.length-1][i]);
}
return res;
}
}
|
总结
核心就在于不能每一行都选择最小值，而是要基于上一行进行选择，然后最终的结果需要从最后一行中挑选最小值