【动态规划/路径问题】变形「最小路径和」问题 & 常见 DP 空间优化技巧 ...

前言

今天是我们讲解「动态规划专题」中的 路径问题 的第四天。

我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。

路径问题 我会按照编排好的顺序进行讲解（一天一道）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 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

<= triangle[i][j] <=

进阶：

你可以只使用

的额外空间（n 为三角形的总行数）来解决这个问题吗？

动态规划解法

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

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

2
3 4
6 5 7
4 1 8 3

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

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

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

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

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

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

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

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

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

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

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

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

那么

（最后一行的每列的路径和的最小值）就是答案。

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

2
3 4
6 5 7
4 1 8 3

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

• 每一行 i 具有 i+1 个数字
• 只要不是第一列（j!=0）位置上的数，都能通过「左上方」转移过来
• 只要不是每行最后一列（j!=i）位置上的数，都能通过「上方」转移而来

同时，这样的分析/转移过程，是可以推广并覆盖所有位置的。

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

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

PS. 由于题目的「进阶」部分要求我们使用

空间复杂度。那么三叶先写个

解法好了。

代码：

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;
    }
}

• 时间复杂度：

• 空间复杂度：

进阶

从我们递推过程可以发现，在求第 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;
    }
}

事实上，这道题的空间还可以优化到

：利用输入数据的空间进行状态转移。

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

总结

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

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

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

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

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

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

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

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

路径问题（目录）

62.不同路径（中等）：路径问题第一讲

63.不同路径 II（中等）：路径问题第二讲

64.最小路径和（中等）：路径问题第三讲

120.三角形最小路径和（中等）：本篇

931.下降路径最小和（中等）

1289.下降路径最小和 II（困难）

1575.统计所有可行路径（困难）

576.出界的路径数（中等）

1301.最大得分的路径数目（困难）

欢迎补充 ~

最后

这是我们「刷穿 LeetCode」系列文章的第 No.120 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。