三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解:

使用动态规划解法,三个步骤:

  1. 定义状态, dp[i] [j]为第i行,包含第j列的最小三角形路径和。
  2. 定义初始值,假设我们dp数组从1 1开始取值,则dp[0] [0] = 0; dp[1] [1]就是 三角形[0] [0],也就是三角形的顶部。
  3. 定义动态转移方程,
    • dp[i] [j] 当 j 是第一列时,则为dp[i - 1] [j] + 三角形[i] [j].
    • 当 j 为最后一列时, 则dp[i] [j] 为dp[i - 1] [j - 1].
    • 当j 不是第一列也不是最后一列时, dp[i] [j]为上一行两个相邻列的最小值。

代码如下:

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

        if (triangle == null || triangle.size() == 0) return 0;
        if (triangle.size() == 1) return triangle.get(0).get(0);
  
        // 定义状态 dp[i][j] 代表到第 i 行,第 j 列 的最小路径和
        int[][] dp = new int[triangle.size() + 1][triangle.get(triangle.size() - 1).size() + 1];

        // 初始值
        dp[0][0] = 0;
        dp[1][1] = triangle.get(0).get(0);

        // 状态转移方程
        int result = Integer.MAX_VALUE;
        for (int i = 2; i <= triangle.size(); i++) {
            List <Integer> list = triangle.get(i - 1);

            for (int j = 1; j <= list.size(); j++) {
                if (j == 1){
                    // 最左
                    dp[i][j] = dp[i - 1][1] + list.get(0);
                }else if (j == list.size()){
                    // 最右
                    dp[i][j] = dp[i-1][j-1] + list.get(j - 1);
                }else {
                    // 中间
                    dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + list.get(j - 1);
                }

                if (i == triangle.size()) {
                    result = Math.min(result,dp[i][j]);
                }
            }
        }

        return result;
    }

时间复杂度 : O(N)

空间复杂度 : O(M * N) 因为用到了额外的二维数组存储元素。 M N分别为三角形的行数和列数。

优化:

上述算法中,我们用到了二维数组, 用来存储矩阵各个点的最小路径, 通过观察发现, 我们计算dp[i] [j] 时,好像只用到了dp[i - 1] […]中的数值,是否可以将空间复杂度由之前的 M * N优化至 O(N)呢,下边我们来做此尝试。

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

        // 定义状态 dp[i] 代表当前行,第 i 列 的最小路径和
        int[] dp = new int[triangle.size()];

        // 初始值
        dp[0] = 0;
        dp[1] = triangle.get(0).get(0);

        // 状态转移方程
        int result = Integer.MAX_VALUE;
        for (int i = 2; i <= triangle.size(); i++) {
            List <Integer> list = triangle.get(i - 1);

            for (int j = list.size(); j > 0; j--) {
                if (j == 1){
                    // 最左
                    dp[j] = dp[1] + list.get(0);
                }else if (j == list.size()){
                    // 最右
                    dp[j] = dp[j-1] + list.get(j - 1);
                }else {
                    // 中间
                    dp[j] = Math.min(dp[j-1], dp[j]) + list.get(j - 1);
                }

                if (i == triangle.size()) {
                    result = Math.min(result,dp[j]);
                }
            }
        }

        return result;
    }

做此优化时 ,内部的遍历需要从后往前遍历,因为从前往后,争取的值会被覆盖掉,如下图:

截屏2020-04-28下午4.23.56

最终计算出来的结果是15,导致不正确。

所以需要从后往前遍历,正确的值不会被覆盖掉,如下图:

截屏2020-04-28下午4.24.00

值不会被覆盖,可以得到争取的值 11.

算法时间复杂度仍然是 : O(N)

空间复杂度由之前的O(N * M) 降低为 O(N).