120. 三角形最小路径和

状态定义：dp[i][j] 表示到达 （i，j）处的最小路径和

问题目标：max(dp数组的最后一行的元素)

状态转移：这种题目有两种求解方式，自底向上和自顶向下。在这里采用的是自顶向下。同时说明一下，此处的三角形是以下三角的形式存储的。dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]

状态初始化：j = 0 和 i == j 处是累加的

时间复杂度：O(m * n)

空间复杂度：O(m * n) ——可优化

原始代码

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m - 1).size();
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i < j){
                    continue;
                }
                if(i == 0 && j == 0){
                    dp[i][j] = triangle.get(i).get(j);
                    continue;
                }
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
                    continue;
                }
                if(i == j){
                    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);
            }
        }
        int ans = dp[m-1][0];
        for(int i = 1; i < n; i++){
            ans = Math.min(ans, dp[m-1][i]);
        }
        return ans;
    }
}

引入滚动数组优化空间复杂度，i & 1

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m - 1).size();
        int[][] dp = new int[2][n];
        dp[0][0] = triangle.get(0).get(0);
        for(int i = 1; i < m; i++){
            for(int j = 0; j <= i; j++){
                if(i == 0 && j == 0){
                    dp[i & 1][j] = triangle.get(i).get(j);
                    continue;
                }
                if(j == 0){
                    dp[i & 1][j] = dp[(i - 1) & 1][j] + triangle.get(i).get(j);
                    continue;
                }
                if(i == j){
                    dp[i & 1][j] = dp[(i-1) & 1][j-1] + triangle.get(i).get(j);
                    continue;
                }
                dp[i & 1][j] = Math.min(dp[(i - 1) & 1][j], dp[(i -1) & 1][j-1]) + triangle.get(i).get(j);
            }
        }
        int ans = dp[(m-1) & 1][0];
        for(int i = 1; i < n; i++){
            ans = Math.min(ans, dp[(m - 1) & 1][i]);
        }
        return ans;
    }
}