前言
今天是我们讲解动态规划专题中的 路径问题 的第四天。
我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我会按照编排好的顺序进行讲解（一天一道）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 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），但在某些题下则是必须的。
路径问题（目录）
62.不同路径（中等）：路径问题第一讲
63.不同路径 II（中等）：路径问题第二讲
64.最小路径和（中等）：路径问题第三讲
120.三角形最小路径和（中等）：本篇
931.下降路径最小和（中等）
1289.下降路径最小和 II（困难）
1575.统计所有可行路径（困难）
576.出界的路径数（中等）
1301.最大得分的路径数目（困难）
欢迎补充 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.120 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
