LeetCode——三角形最小路径和

NO.120 三角形最小路径和中等

思路一：动态规划 dp[i][j]含义：到triangle[i][j]元素为止的最小路径和。

初始化：dp[0][0]=triangle[0][0]，因为第一行只有一个元素。

状态转移：所以dp[i][j]=min(dp[i-1][j]+d[i-1][j-1])+triangle[i][j]，需要注意特殊情况：j==0没有j-1、j==i没有j。

最后取出dp数组的最后一行，从中找出最小的路径和。

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) return 0;
    int r = triangle.size();
    int c = triangle.get(r - 1).size();
    //初始化
    int[][] dp = new int[r][c];
    dp[0][0] = triangle.get(0).get(0);
    //状态转移
    for (int i = 1; i < r; i++) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
            } else if (j == i) {
                dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
    }
    //最小路径和一定在dp数组最后一行中
    int ans = Integer.MAX_VALUE;
    for (int e : dp[r - 1]) {
        ans = Math.min(ans, e);
    }
    return ans;
}

时间复杂度：O(r^2) 空间复杂度：O(r^2)

优化空间到O(r) 每次填写一下层的时候，只关心dp[i - 1][j]和dp[i - 1][j - 1]用两个变量right、left记录上一层的这两个值。

dp数组初始化为[r]大小，状态转移方程不变，复用这个一维dp数组。

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) return 0;
    int r = triangle.size();
    //初始化
    int[] dp = new int[r];
    dp[0] = triangle.get(0).get(0);
    //记录dp[i - 1][j]和dp[i - 1][j - 1]
    int left = 0, right;
    //状态转移
    for (int i = 1; i < r; i++) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j <= i; j++) {
            right = dp[j];
            if (j == 0) {
                dp[j] = right + row.get(j);
            } else if (j == i) {
                dp[j] = left + row.get(j);
            } else {
                dp[j] = Math.min(left, right) + row.get(j);
            }
            left = right;
        }
    }
    //找出最小的路径和
    int ans = Integer.MAX_VALUE;
    for (int e : dp) {
        ans = Math.min(ans, e);
    }
    return ans;
}

时间复杂度：O(r^2) 空间复杂度：O(r)

自底向上DP 从下向上找最小路径，最终找到最上层的一个元素，得到最小路径和。

可以免除边界判断，不需要记录上一层的两个变量。

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) return 0;
    int r = triangle.size();
    //因为自底向上，所以计算最后一行i的时候，需要i+1行的最小路径和。
    int[] dp = new int[r + 1];
    //状态转移
    for (int i = r - 1; i >= 0; i--) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
        }
    }
    return dp[0];
}

时间复杂度：O(r^2) 空间复杂度：O(r)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.120 三角形最小路径和 中等

NO.120 三角形最小路径和中等