leetcode120_三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路：

动态规划   i可以由上一行i和上一行i-1位置到达

找到最后一行最小的  位置

dp[i][j]表示达到第i行第j个数字的最小值   dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+list.get(j)  这是一般位置  开头和结尾做处理

public static int minimumTotal(List<List<Integer>> triangle) {
		int n = triangle.size();  //行
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return triangle.get(0).get(0);
        }
        
        int[][] dp = new int[n][n];
        
        dp[0][0] = triangle.get(0).get(0);
        int res = Integer.MAX_VALUE;
        for(int i=1;i<n;i++){
            List<Integer> list = triangle.get(i);   //得到每一行的集合
            for(int j=0;j<=i;j++){
                if(j==0){
                    //0位置       开头
                    dp[i][j]=dp[i-1][j]+list.get(j);
                }else if(j == i){    //i行i列了  比上一行多一个 只能由上一行的j-1位置得到
                    // i和j相等位置   结尾
                    dp[i][j]=dp[i-1][j-1]+list.get(j);
                }else{
                    // 中间位置
                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+list.get(j);
                }
                if(i == n-1){
                    // 从最后一行找最小值
                    res = Math.min(res,dp[i][j]);
                }
            }
        }
        return res;
    }

2.简化空间

dp[k]  表示到达某行第k个位置获得的最小值   dp[j]没有更新时  表示的是上一行的j位置获得的最小值  从后往前遍历  避免计算同一行的dp[j]  对dp[j+1]造成了影响  因为dp[j+1]需要用到dp[i]

public int minimumTotal2(List<List<Integer>> triangle) {
        int n = triangle.size();
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return triangle.get(0).get(0);
        }
        
        int[] dp = new int[n];   //dp[k]  表示到达某行第k个位置获得的最小值   dp[j]没有更新时  表示的是上一行的j位置获得的最小值  
        dp[0] = triangle.get(0).get(0);
        int res = Integer.MAX_VALUE;
        
        for(int i=1;i<n;i++){
            List<Integer> list = triangle.get(i);
            
            for(int j=list.size()-1;j>=0;j--){   //从后往前遍历  避免计算同一行的dp[j]  对dp[j+1]造成了影响  因为dp[j+1]需要用到dp[i]
               
                if(j==0){   //dp[j]没有更新时  表示的是上一行的j位置获得的最小值                  
                    dp[j]=dp[j]+list.get(j);
                }else if(j == list.size()-1){
                	dp[j]=dp[j-1]+list.get(j);
                }else{                   
                    dp[j]=Math.min(dp[j-1],dp[j])+list.get(j);                   
                }
           
                if(i == n-1){
                    res = Math.min(res,dp[j]);
                }
            }
        }
        return res;
    }