题目

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

  • 示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:

输入:triangle = [[-10]]
输出:-10

进阶:

你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?

思路一:失败的贪心算法

思路

看到这一题,我就在想,这是一道贪心,还是一道 DP 问题呢?

于是脑海中首先蹦出了贪心的解法。

整体流程如下:

(1)第一次选择,只有两种方式,要么向下,要么向下右。

(2)我们选择两者中最短的一个,作为下一次的结果

(3)依次根据 (1)(2),一直到结尾。

java 实现

java 实现如下:

public int minimumTotal(List<List<Integer>> triangle) {
    int[] greedy = new int[triangle.size()+1];
    greedy[0] = triangle.get(0).get(0);
    int ix = 0;
    // 第一个元素
    for(int i = 1; i < triangle.size(); i++) {
        // 针对第一步不变的元素
        ix = next(triangle, i, ix, greedy);
    }
    int size = triangle.size();
    return greedy[size-1];
}

// 下一步的处理逻辑
// 选择 i 和 i+1,选择更小的,并且返回新的 index
// 从 2 开始
private int next(List<List<Integer>> triangle,
                  int level, int preIndex,
                  int[] dp) {
    List<Integer> list = triangle.get(level);
    int minVal = list.get(preIndex);
    int minIndex = preIndex;
    int nextVal = list.get(preIndex+1);
    if(nextVal < minVal) {
        minVal = nextVal;
        minIndex = preIndex+1;
    }
    dp[level] = dp[level-1] + minVal;
    return minIndex;
}

反思

当然,贪心算法这样用肯定是不对的。

因为我们只顾及眼前一步的利益,而不是放眼全局,所以结果往往不是最优解。

思路2:动态规划

思路

实际上当我们能想到使用 DP 去解这一题的时候,已经成功了一半了。

我们只需要依次解决下面的问题即可:

(1)初始值是什么?

(2)递推公式是什么?

(3)边界情况的考虑

(4)最后结果的获取

初始值

如果我们创建 dp[][],那么初始值显然就是第一个元素 dp[0][0] = triangle.get(0).get(0);

递推公式

这一题实际上和有一题的从左上角到右下角的路径非常类似。

我们从上往下,实际上对于当前的一个位置 f[i][j] 而言,只可能从 f[i-1][j](正上方),或者 f[i-1][j-1](正上方的左边一格)移动到当前位置。

我们就是要找到而这种最短的一个路径,作为后续路径:

f[i][j] = Math.min(f[i-1][j], f[i-1][j-1]) + triangle.get(i).get(j);

边界的考虑

如果 i = 0,也就是当前行在最左边,那么到这里实际上只有一种可能,那就是正上方过来。

dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);

如果 i = i(也就是当前行的最右边),那么只能从上一行的最右边向下再向右一格得到:

dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);

最后的结果

我们把所有的结果都放在 dp 数组中,最后遍历数组,获取最小的就是最后的答案。

java 实现

java 实现如下:

public int minimumTotal(List<List<Integer>> triangle) {
    int size = triangle.size();
    int[][] dp = new int[size][size];

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

    // 遍历(i 对应层级)
    for(int i = 1; i < size; i++) {
        //1. 如果为 0,上一层也只能为 0
        dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
        //2. 中间部分
        for(int j = 1; j < i; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle.get(i).get(j);
        }
        //3. 如果为 i
        dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
    }

    // 遍历获取最小的一个
    int minTotal = dp[size - 1][0];
    for (int i = 1; i < size; i++) {
        minTotal = Math.min(minTotal, dp[size - 1][i]);
    }
    return minTotal;
}

效果也不错:

Runtime: 1 ms, faster than 96.81% of Java online submissions for Triangle.
Memory Usage: 38.8 MB, less than 92.94% of Java online submissions for Triangle.

思路3:从下向上,滚动数组优化

O(n) 空间的思路 1

当然,让我们回顾一下题目。

题目中问道,我们可以使用 O(n) 的额外空间来实现吗?

答案是肯定的,因为从地推公式 f[i][j] = Math.min(f[i-1][j], f[i-1][j-1]) + triangle.get(i).get(j); 可以知道,我们不必存放所有的元素,只需要保留上面的 2 个元素就行。

此处就不做展开。

O(n) 空间的思路 2

我们重点要说的是,自下向上,使用 O(n) 额外空间的解决方案。

1
2 3
4 5 6
7 8 9 10

如果从下往上处理的话:

1
|\
2 3
|\|\
4 5 6
|\|\|\  
7 8 9 10

我们看 [7,8,9,10] 这几个元素,因为只能向下移动,或者下面的向右一格。

往上去的话,就是 [7,8] 对应4,[8,9] 对应 5,[9,10] 对应 6。

所以我们可以认为 4 这个位置,只需要取 [7,8] 位置中较小的值,然后加上当前值即可。可以一次类推,直到最上面的一个值,就是我们想要的结果。

java

我们直接把最后一行初始化到 dp 数组中,额外空间为 O(n)。

这种实现更加优雅,是我个人非常喜欢的一种实现方式。

public int minimumTotal(List<List<Integer>> triangle) {
    int size = triangle.size();
    // 最后一行,初始化到 dp
    int[] dp = new int[size];

    for(int i = 0; i < size; i++) {
        dp[i] = triangle.get(size-1).get(i);
    }
    for(int i = size-2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
        }
    }
    return dp[0];
}

效果:

Runtime: 1 ms, faster than 96.81% of Java online submissions for Triangle.
Memory Usage: 39.4 MB, less than 25.02% of Java online submissions for Triangle.

思路4:复用传入的数组

思路

如果问你,你可以不借助额外的空间,能实现最短路径的获取吗?

答案也是可以的,当然,我们不能无中生有。

整体解法思路和3类似。

我们做的,就是把值放在了入参数组中而已。

java 实现

public int minimumTotal(List<List<Integer>> triangle) {
    int size = triangle.size();
    // list 有太多的越界限制,导致性能很差。
    for(int i = size-2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            List<Integer> list = triangle.get(i);
            int min = Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1)) + triangle.get(i).get(j);
            list.set(j, min);
        }
    }
    return triangle.get(0).get(0);
}

效果:

Runtime: 4 ms, faster than 36.07% of Java online submissions for Triangle.
Memory Usage: 38.7 MB, less than 92.94% of Java online submissions for Triangle.

可以发现这种方法的空间复杂度很低,但是性能一般。

个人猜测,应该是数组各种越界判断导致的。

小结

希望本文对你有帮助,如果有其他想法的话,也可以评论区和大家分享哦。

各位极客的点赞收藏转发,是老马持续写作的最大动力!

参考资料

https://leetcode-cn.com/problems/triangle/