【动态规划/路径问题】变形「最小路径和」问题 & 常见 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 <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1−104-10^4−104 <= triangle[i][j] <= 10410^4104

进阶：

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

动态规划解法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通过观察可以发现以下性质（令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 原题链接和其他优选题解。

网址：【动态规划/路径问题】变形「最小路径和」问题 & 常见 DP 空间优化技巧 ...｜刷题打卡 https://www.yuejiaxmz.com/news/view/566646

相关内容

算法动态规划01背包问题
【创新未发表】基于鱼鹰OOA求解带时间窗的骑手外卖配送路径规划问题，最优路径成本附Matlab代码
旅行商问题（动态规划方法，超级详细的）
动态规划之空间优化与总结回顾
旅行商问题，车辆路径问题的数学规划模型
动态规划的时间复杂度优化
MATLAB 旅行商问题（动态规划法）程序
旅游省钱大法：加权最短路径
动态规划问题dp问题以及经典问题
刷题实践选题：小U生活事件快乐值最大化问题

随便看看