120. Triangle

问题
Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

动态规划，先将最左侧一列的值算出。
然后[i+1][j+1]根据[i][j+1]和[i][j]得出。
该动态规划表应是为三角形。
因此当i等于j时，[i+1][i+j]的数值只根据[i][j]得出。

例子：
代码里插入了一个print方法打印动态规划表。
当输入列表 [[2],[3,4],[6,5,7],[4,1,8,3]] 时：
其动态规划表为：

• 2, 0, 0, 0,
• 5, 6, 0, 0,
• 11, 10, 13, 0,
• 15, 11, 18, 16,

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        int min = Integer.MAX_VALUE;
        dp[0][0] = triangle.get(0).get(0);
        
        for (int i = 0; i < triangle.size()-1; i++){
            dp[i+1][0] = dp[i][0] + triangle.get(i+1).get(0);
        }        
        
        for (int i = 0; i < triangle.size()-1; i++){
            for (int j = 0; j <= i; j++){
                
                if ( i == j ){
                    dp[i+1][j+1] = dp[i][j] + triangle.get(i+1).get(j+1);
                }
                else{
                    dp[i+1][j+1] = Math.min(dp[i][j] + triangle.get(i+1).get(j+1),
                                        dp[i][j+1] + triangle.get(i+1).get(j+1));
                }
                
            }
        }
        //print(dp);
        for (int k = 0; k < triangle.size(); k++){
            min = Math.min(dp[triangle.size()-1][k],min);
        }
        return min;
    }
    
    private void print(int[][] text){
        for (int i = 0; i <text.length; i++){
            for (int j = 0; j < text[0].length; j++){
                System.out.print(text[i][j]+", ");
            }
            System.out.println();
        }
    }

}