version : 2022-04-04

/**
1. 三角形可以向下走, 每走一步累加当前位置的和, 求走完全程的路径的最小值
2. 已经每次只依赖上一次的路径, 所以可以用动态规划
3. 3.1 状态定义: f[i][j] 是走到第i行第j列的路径的和的最小值
   3.2 状态计算: 可以从f[i-1][j] 和 f[i-1][j-1]走到当前节点, 所以 f[i][j] = MIN(f[i-1][j], f[i-1][j-1]) + r[i][j]
4. 初始状态为 f[~][~] = MAX_VALUE, 第一个值f[0][0] = 0 作为初始化;  结果为MIN(f[n][~])
*/

class Solution {
    public int minimumTotal(List<List<Integer>> t) {
        int n = t.size();
        int[][] f = new int[n+1][n+1];
        for (int i = 0 ; i <= n ; i++) Arrays.fill(f[i], Integer.MAX_VALUE);
        f[0][0] = 0;

        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= i; j++) {
                f[i][j] = Math.min(f[i-1][j], f[i-1][j-1]) + t.get(i-1).get(j-1);
            }
        }

        return Arrays.stream(f[n]).min().getAsInt();
    }
}

version at: 2020-01-26

//1.状态定义：f[i][j]以坐标为 i，j 结尾的最小值
//2.状态计算：f[i][j] = MIN(f[i-1][j], f[i-1][j-1]) + triangle[i][j]
//3.边界：f[~][~] = INF
//4.优化为滚动数组&1 即可

class Solution {

        public int minimumTotal(List<List<Integer>> triangle) {

        if (triangle == null || triangle.get(0) == null) return 0;

        int n = triangle.size();
        int m = triangle.get(n-1).size();

        int[][] f = new int[2][m+2];
        Arrays.fill(f[0], Integer.MAX_VALUE);
        Arrays.fill(f[1], Integer.MAX_VALUE);
        f[1][1] = triangle.get(0).get(0);
        for (int i = 2 ; i <= n ; i++){
            for (int j = 1 ; j <= i ; j++){
                f[i&1][j] = Integer.MAX_VALUE;
                f[i&1][j] = Math.min(f[i-1&1][j], f[i-1&1][j-1]) + triangle.get(i-1).get(j-1);
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= m ;i++){
            res = Math.min(res, f[n&1][i]);
        }
        return res;
    }

    public int minimumTotal2(List<List<Integer>> triangle) {

        if (triangle == null || triangle.get(0) == null) return 0;

        int n = triangle.size();
        int m = triangle.get(n-1).size();


        int[][] f = new int[n+2][m+2];


        // for (int i = 1 ; i <= n ; i++){  没初始化左边0那列和上面0那行
        //     for (int j = 1 ; j <= m ; j ++){
        //         f[i][j] = i >= j ? triangle.get(i-1).get(j-1) : Integer.MAX_VALUE;
        //     }
        // }

        for (int i = 0 ; i <= n ; i++){
            for (int j = 0 ; j <= m ; j ++){
                f[i][j] = i >= j && i>=1 && j>=1? triangle.get(i-1).get(j-1) : Integer.MAX_VALUE;
            }
        }

        for (int i = 2 ; i <= n ; i++){
            for (int j = 1 ; j <= i ;j++){
                f[i][j] += Math.min(f[i-1][j], f[i-1][j-1]);
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= m ;i++){
            res = Math.min(res, f[n][i]);
        }
        return res;
    }
}