120. 三角形最小路径和 两种动态规划
程序员文章站
2022-03-23 11:27:24
120. 三角形最小路径和难度:中等 2020/7/14每日一题打卡√题目描述解题思路这个是我自己完全没看答案写出来的,用的是自顶向下的递归,然后一看题解?为啥别人写的都那么短,噢原来别人写的都是自底向上的,这样可以省去判断边界条件1、自顶向下的思路很简单啦,就是贪心加动态规划的思想,对于每个位置的元素,选择从上面一层到这一层的两个路径中最小的,这样到底层就能得到所有可能的路径和,取最小的。这样做其实做复杂了,因为从顶部开始选择的时候,其实是不知道选哪个点会得到全部最小值的,还需要最后的结...
120. 三角形最小路径和
难度:中等 2020/7/14每日一题打卡√
题目描述
解题思路
这个是我自己完全没看答案写出来的,用的是自顶向下的递归,然后一看题解?为啥别人写的都那么短,噢原来别人写的都是自底向上的,这样可以省去判断边界条件
1、自顶向下的
思路很简单啦,就是贪心加动态规划的思想,对于每个位置的元素,选择从上面一层到这一层的两个路径中最小的,这样到底层就能得到所有可能的路径和,取最小的。
这样做其实做复杂了,因为从顶部开始选择的时候,其实是不知道选哪个点会得到全部最小值的,还需要最后的结果来判断。但是从底向上就可以知道选哪个最小,有个图做的很好。
/*
* 120. 三角形最小路径和
* 2020/7/14
*/
public int minimumTotal(List<List<Integer>> triangle) {
int min = Integer.MAX_VALUE,n = triangle.size();
int[][] dp = new int[n][n];
dp[0][0] = triangle.get(0).get(0); //初始化第一行
for (int i = 1; i < n; i++) { //一行一行计算
List<Integer> row = triangle.get(i);
for (int j = 0; j <= i; j++) {
if(j == 0 ) { //如果在两端,直接相加得到最小路径
dp[i][j] = dp[i-1][j] + row.get(j);
}else if(j == i) {
dp[i][j] = dp[i-1][j-1] + row.get(j);
}
else {
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j+1]) + row.get(j);
}
}
}
for (int i = 0; i < n; i++) {
min = dp[n-1][i] < min?dp[n-1][i]:min;
}
return min;
}
2、自底向上的动态规划
就像上面那个图,只用O(n)的辅助空间,滚动数组
初始化为最后一层 4 1 8 3
然后从倒数第二层开始动态规划,倒数第二层6 5 7
对于6,下标是0,选择dp[0] 和dp[1]里最小的作为路径,相加,比如6就选择1,然后覆盖dp[0]的值成了7,但是不影响后续数字的计算
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
if(n == 0)
return 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = triangle.get(n-1).get(i);
}
for (int i = n-2; i >= 0; i--) {
List<Integer> row = triangle.get(i);
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j],dp[j+1]) + row.get(j);
}
}
return dp[0];
}
本文地址:https://blog.csdn.net/hh155715/article/details/107340991
上一篇: Android常用UI控件的使用
下一篇: 游戏配音中要满足这些要求,才能提高质量