变形「最小路径和」问题 & 常见 DP 空间优化技巧

题目描述

这是 LeetCode 上的120. 三角形最小路径和，难度为 Medium。

给定一个三角形 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

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• −104-10^4−104 <= triangle[i][j] <= 10410^4104

进阶：

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

动态规划解法

对于此类（具有形状的）题目，如果并不熟练，我的建议是先画出真实的数组分布情况。

以样例一的数据为例，真实的 triangle 分布应该是：

2
3 4
6 5 7
4 1 8 3

先把图画出来，之后我们再来分析，这道题我们是如何想到 DP 的。

如何确定一道题目是否可以用 DP 解决，我们要从有无后效性进行分析。

首先，既然是从上到下的路径，那么最后一个点必然是落在最后一行。

对于最后一行的某个位置的值，根据题意只能从上一行的某一个位置或者某两个位置之一转移而来。

同时，我们只关注前一位的累加值是多少，而不关心这个累加值结果是由什么路径而来的。

这显然就满足了「无后效性」的定义：我们转移某个状态需要用到某个值，但是并不关心该值是如何而来的。

更加的学术表达是：当前某个状态确定后，之后的状态转移与之前的决策无关

因此我们可以确定使用 DP 进行求解。

接下来的问题是，我们该如何确定 状态定义 呢？

通常我们会根据 结尾 和 答案 来猜 DP 的状态定义。

所谓的 结尾 通常就是指 最后一步。

对于本题，我们结合两者可以猜一个 DP 状态： f[i][j] 代表到达某个点的最小路径和。

那么 min(f[n−1][i])min(f[n-1][i])min(f[n−1][i]) （最后一行的每列的路径和的最小值）就是答案。

再结合我们刚刚画的分布图：

2
3 4
6 5 7
4 1 8 3

通过观察可以发现以下性质（令i为行坐标，j为列坐标）：

• 每一行 i 具有 i+1 个数字
• 只要不是第一列（j!=0）位置上的数，都能通过左上方转移过来
• 只要不是每行最后一列（j!=i）位置上的数，都能通过上方转移而来
• 同时，这样的分析/转移过程，是可以推广并覆盖所有位置的。

至此，整个过程都没有问题，状态转移方程也能不重不漏的枚举到每一条路径。

因此这个 DP 状态定义可用。

PS：由于题目的「进阶」部分要求我们使用 O(n)O(n)O(n) 空间复杂度。那么三叶先写个 O(n2)O(n^2)O(n2) 解法好了。

代码：

class Solution {
    public int minimumTotal(List<List<Integer>> tri) {
        int n = tri.size();
        int ans = Integer.MAX_VALUE;
        int[][] f = new int[n][n];
        f[0][0] = tri.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                int val = tri.get(i).get(j);
                f[i][j] = Integer.MAX_VALUE;
                if (j != 0) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + val);
                if (j != i) f[i][j] = Math.min(f[i][j], f[i - 1][j] + val);
            }
        }
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[n - 1][i]);
        return ans;
    }
}

• 时间复杂度：O(n2)O(n^2)O(n2)
• 空间复杂度：O(n2)O(n^2)O(n2)

进阶
从我们递推过程可以发现，在求第 i 行的状态时只依赖于第 i-1 行的状态。

那么我们不需要存储所有行的状态值（动规值），可以对空间进行优化。

通常 DP 的空间优化思路有两种：

• 滚动数组
• 根据状态依赖调整迭代/循环的方向

其中滚动数组的优化方式，是我最推荐的。

因为没有任何的思维难度，只需要将其中一维直接改成 2，任何在将维的 f[i] 改成 f[i&1] 或者 f[i%2] 即可（推荐前者，在不同架构的机器上，运算效率更加稳定）。

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

事实上，这道题的空间还可以优化到 O(1)O(1)O(1)：利用输入数据的空间进行状态转移。

这部分的编码实现不难，就当是我给你留的作业吧 ~

总结

这是一道毫无疑问的「DP 裸题」，但我仍然希望你去抠我题解写的每一步思考过程。

想想我们以前是怎么学数学的，每个知识点必然是用很简单的模板题来教学的。

只有这样我们才能学会这个知识点，才能学到知识点里的精髓，而不是被细节冲昏头脑。

对于这道题的「完整思考」过程，我们应该做到每一步都是「有理有据」，由逻辑推导而来。

而这些分析技巧我都在 路径问题第一讲 跟你讲过。

而且随着 动态规划系列 的进行，我们还会不断强化这些分析方法。

此外，我还给你介绍了常规的 DP 空间手段，希望你能加深理解 ~

在这道题上空间优化是可选的（不优化空间也能 AC），但在某些题下则是必须的。

作者：宫水三叶的刷题日记
链接：https://juejin.cn/post/6938674367362826248
来源：掘金