package leetcode;

import java.util.ArrayList;
import java.util.List;

public class demo_120 {
    //动态规划
    public int minimumTotal(List<List<Integer>> triangle) {
        int sum;
        int[][] dp=new int[triangle.size()][triangle.get(triangle.size()-1).size()];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<dp.length;i++) {
            for(int j=0;j<=triangle.get(i-1).size();j++) {
                if(j==0) {
                    dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
                    continue;
                }
                if(j==triangle.get(i-1).size()) {
                    dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
                    continue;
                }
                dp[i][j]=Math.min(dp[i-1][j], dp[i-1][j-1])+triangle.get(i).get(j);
            }
        }
        sum=dp[dp.length-1][0];
        //求出最后一层的最小值即是最终结果
        for(int i=1;i<dp[dp.length-1].length;i++) {
            if(sum>dp[dp.length-1][i]) {
                sum=dp[dp.length-1][i];
            }
        }
        System.out.println(sum);
        return sum;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<List<Integer>> triangle=new ArrayList<List<Integer>>();
        demo_120 d120=new demo_120();
        List<Integer> l1=new ArrayList<Integer>();
        l1.add(2);
        List<Integer> l2=new ArrayList<Integer>();
        l2.add(3);l2.add(4);
        List<Integer> l3=new ArrayList<Integer>();
        l3.add(6);l3.add(5);l3.add(7);
        List<Integer> l4=new ArrayList<Integer>();
        l4.add(4);l4.add(1);l4.add(8);l4.add(3);
        triangle.add(l1);
        triangle.add(l2);
        triangle.add(l3);
        triangle.add(l4);
        d120.minimumTotal(triangle);
    }

}