120. Triangle

java 解法 阶梯形式 动态规划保存 每个位置取上面 或者斜上面的数 重叠则需要把小的保存到flag 中 然后到最后一层则直接看那个数最小 则为最小路径

class Solution {
//消耗的空间过大
    public int minimumTotal(List> triangle) {
        int ans = Integer.MAX_VALUE;
        int flag[][] = new int[triangle.size()][triangle.size()];
        flag[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.get(i).size(); j++)
                flag[i][j] = Integer.MAX_VALUE;
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j - 1 >= 0)
                    flag[i][j] = triangle.get(i).get(j) + flag[i - 1][j-1];
                if(j != triangle.get(i).size()-1)
                    flag[i][j] = Math.min(flag[i][j], triangle.get(i).get(j) + flag[i - 1][j]);
            }
        }
        int x = triangle.size();
        for(int j = 0 ; j < x ; j++) {
            ans = Math.min(flag[x-1][j], ans);
        }
        return ans;
    }
}

优化：

//空间优化： 每次计算一层(i,j)位置的数到底部的最小距离和时，当前层只跟它的下一层有关系，所以我们只用保留下一层的结果
        //就可以，用一维数组，一直更新这个一维数组就可以
class Solution {
    public int minimumTotal(List> triangle) {
    int row=triangle.size();
        int column=triangle.get(row-1).size();//最后一行数最多，作为数组列数来用
        int dp[]=new int[column];
        for(int i=0;i<column;i++)
            dp[i]=triangle.get(row-1).get(i);//最后一行到底部的距离就等于它自身的值
        for(int i=row-2;i>=0;i--) {
            for(int j=0;j<=i;j++) {
                dp[j]=Math.min(dp[j],dp[j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0];
}
}

python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        flag = [None]* len(triangle)
        n = len(triangle)-1
        for i in range(len(triangle)):
            flag [i] = triangle[n][i]
        n = n - 1
        while n >= 0 :
            for j in range(len(triangle[n])):
                temp = flag[j]
                if(j < len(triangle[n])):
                    temp = min(temp, flag[j+1])
                flag[j] = temp + triangle[n][j]
            n = n - 1 
        return flag[0]