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

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

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