欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

120. 三角形最小路径和 两种动态规划

程序员文章站 2022-03-23 11:27:24
120. 三角形最小路径和难度:中等 2020/7/14每日一题打卡√题目描述解题思路这个是我自己完全没看答案写出来的,用的是自顶向下的递归,然后一看题解?为啥别人写的都那么短,噢原来别人写的都是自底向上的,这样可以省去判断边界条件1、自顶向下的思路很简单啦,就是贪心加动态规划的思想,对于每个位置的元素,选择从上面一层到这一层的两个路径中最小的,这样到底层就能得到所有可能的路径和,取最小的。这样做其实做复杂了,因为从顶部开始选择的时候,其实是不知道选哪个点会得到全部最小值的,还需要最后的结...

120. 三角形最小路径和

难度:中等 2020/7/14每日一题打卡√
题目描述
120. 三角形最小路径和  两种动态规划
解题思路
这个是我自己完全没看答案写出来的,用的是自顶向下的递归,然后一看题解?为啥别人写的都那么短,噢原来别人写的都是自底向上的,这样可以省去判断边界条件

1、自顶向下的

思路很简单啦,就是贪心加动态规划的思想,对于每个位置的元素,选择从上面一层到这一层的两个路径中最小的,这样到底层就能得到所有可能的路径和,取最小的。
这样做其实做复杂了,因为从顶部开始选择的时候,其实是不知道选哪个点会得到全部最小值的,还需要最后的结果来判断。但是从底向上就可以知道选哪个最小,有个图做的很好。
120. 三角形最小路径和  两种动态规划

 /*
		     * 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;

		    }

120. 三角形最小路径和  两种动态规划

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];
    }

120. 三角形最小路径和  两种动态规划

本文地址:https://blog.csdn.net/hh155715/article/details/107340991