// @Title: 三角形最小路径和 (Triangle)
// @Author: qisiii
// @Date: 2024-10-14 16:54:12
// @Runtime: 3 ms
// @Memory: 42.6 MB
// @comment: 动态规划
// @flag: GREEN
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp=new int[triangle.size()];
        int min=Integer.MAX_VALUE;
        for(int i=0;i<triangle.size();i++){
            for(int j=i;j>=0;j--){
                if(j==0){
                    dp[j]=dp[j]+triangle.get(i).get(j);
                }else if(j==i){
                    dp[j]=dp[j-1]+triangle.get(i).get(j);
                }else{
                    //从上往下只能是当前和下一个，翻译一下就是从下往上只能是当前或者前一个
                    dp[j]=Math.min(dp[j],dp[j-1])+triangle.get(i).get(j);
                }
            }
        }
        for(int i:dp){
            min=Math.min(i,min);
        }
        return min;
    }
}