【科学派 DP】一份「路径问题从入门到进阶」的究极指南 ...

第一个 DP 系列：路径问题

昨天（2021/03/23）我们完成了第一个【动态规划】专题：路径问题。

整个系列共十讲。

第一讲是在 2021/03/08 发布的，最终章是在 2021/03/23 发布的。

总共持续时长大概是 2 周左右，前面 8 讲都是日更。但后面考虑到每一讲的内容都很多，有些读者会因为学校课程或者工作原因，比较难消化，所以稍稍放缓了更新频率。

由于 DP 很难，所以之后的 DP 系列课程也会按照这样的节奏来推进，大概是 2~3 天更新一篇。中间的休息时间会更新一些难度低一点的内容。

Q & A

在更新「路径问题」期间，收到了不少同学的私信疑问。

当中有一些疑问，我觉得还挺有代表性的，因此整理一下。

Q1：为啥要从「路径问题」入手学 DP，而不是经典的「跳台阶」或者「背包」呢？

A1：之所以选择「路径问题」作为 DP 的第一个系列，是因为「路径问题」很容易进行可视化，我们可以通过观察 DP 的转移过程来看到「最佳路径」是如何被选择出来的。 「背包问题」虽然经典，但是并不好作为入门系列，因为你无法很自然的搞清楚选择最优方案是如何选择出来的。更多的会停留在对「转移」的抽象中。

Q2：好像「路径问题」在 DP 热题里面出现频率不高呢，有必要去学吗？

A2：事实上，「路径问题」在 DP 中出现得一点都不少。也是面试的常见题型。 据我所知「腾讯」和「Hulu」都出过 DP 路径原题。

Q3：学完这个就只能解决 DP 中的「路径问题」吗？DP 相关的题型这么多，学到啥时候是个头呀？

A3：事实上，这个系列课程虽然称为「路径问题」，但只是借助「路径问题」来教大家「通用的解决 DP 的思路」。因此，你掌握了这十讲的「路径问题」的通用技巧，是可以推导到任意的 DP 问题的。

「路径问题」大纲

「第一讲：62.不同路径（中等）」

分享第一种【通用 DP 解决手法】：「经验解法」，以及 DP 求解的五个核心问题：

1. 如何确定可以使用动态规划来求解问题
2. 如何确定本题的状态定义
3. 如何确定状态转移方程
4. 对状态转移的要求是什么
5. 如何分析动态规划的时间复杂度

「第二讲：63.不同路径 II（中等）」

练习篇，主要是为了强化在「第一讲」所教的各种技巧。

通过解决一道新的 DP 题目来感受「第一讲」的 DP 技巧是如何运用到我们的每一步的 DP 思考中的。

强调有了「第一讲」的技巧，每一步都可以做到有理有据。

「第三讲：64.最小路径和（中等）」

通过「最小路径和」问题来分享如何进行「维度合并」来降低”出错风险“和”Debug 难度“。

分享 DP 问题中的一个常用技巧：通过「问题等价变换」来降低编码难度。

「第四讲：120.三角形最小路径和（中等）」

再次强调如何考虑问题的「后效性」。

讲解常见 DP 空间优化技巧：如何通过固定的手法来将

的空间复杂度优化到

。

并通过一道新题再次回顾我们最开始学习的 DP 通用「经验解法」。

「第五讲：931.下降路径最小和（中等）」

在这一节，首先强调对于同类问题，使用「代入解题」思路时的注意点。

以及当我们有一个可行的 DP 解法，但是复杂度过高时，应该如何考虑问题。

强调要将 DP 过程进行「拆分」，从而找到可优化的点在哪里。

「第六讲：1289.下降路径最小和 II（困难）」

练习篇，强化我们在「第五讲」中的「优化指导思想」：

将 DP 过程进行拆分，从而科学的找到可优化的点。降低「朴素 DP」的时间复杂度。

「第七讲：1575.统计所有可行路径（困难）【记忆化搜索】」

强调 DP 的前置思考「记忆化搜索」，以及「记忆化搜索」与 DP 的内在练习。

同时为我们第二种【通用 DP 解决手法】：「技巧解法」开了个头。

「第八讲：1575.统计所有可行路径（困难）【动态规划】」

分享第二种【通用 DP 解决手法】：「技巧解法」。

强调该如何忽略「状态定义」&「转移方程」来求解 DP 问题。

着重分享如何在不实现「记忆化搜索」的前提，将其转化为 DP。

结合最开始教的第一种【通用 DP 解决手法】：「经验解法」，我们就已经掌握了可以解决「所有动态规划」问题的通用方法了。

「第九讲：576.出界的路径数（中等）」

练习篇，强化在「第八讲」分享的第二种【通用 DP 解决手法】：「技巧解法」。

如何通过「记忆化搜索」中的 DFS 函数签名设计，来确定 DP 的「状态定义」。

通过一道新题，强调「技巧解法」的科学性与合理性。

「第十讲：1301.最大得分的路径数目（困难）」

一道「综合性」的 DP 问题，再求「最佳方案」的同时求「最佳方案的方案数」。

回顾我们第一种【通用 DP 解决手法】：「经验解法」，以及对面需要两遍 DP 的综合问题时，该如何考虑。

在最后总结部分，回顾前面学过的所有知识点。

下一个 DP 系列：背包问题

当我们有了「经验解法」和「技巧解法」这两大通用 DP 解决手法之后，科学学习 DP 的下一步应该是接触更多的 DP 模型。

因此，我们将会讲解 DP 系列经典问题：背包问题。

欢迎大家继续学习 ~

寄语

其实写一个「系列文章」还是比较累的，从编排题目到知识点的层层递进，需要考虑的东西很多。

因此为了发挥出「系列文章」的最大价值，我建议大家是「集中时间进行学习」或者「跟着进度」学习，而不是隔了很长时间再去看下一讲。

「系列文章」中题与题之间的关联性很强，很有可能我今天教了你解决题目 A，明天的题目 B 你自己就能解决了。

这是好事，但是并不代表真正掌握了这类题目的本质。

很有可能只是利用了「代入解法」的思维。换个条件，或者为题目套上一个背景，也就解不出来了。

而且从「系列文章」的编排上来说，每一讲都会有新的知识点输出，不存在单纯的「练习课」。

因此十分不建议，某道题目你会了就跳过这一讲的做法。

跟着进度进行学习，对每一篇「系列文章」进行精读，才能将玄学的 DP 变为科学的 DP。

最后，如果你跟完了「路径问题」的所有文章，三叶在这里给你点一个大大的赞 ~ ???

因为确实并不容易，知识点的输出也很密集，建议定期进行回顾与总结哦。

也请你在留言区告诉我，你有很认真的看完「路径问题」，真的就是对三叶的最大鼓励了 ~ ? ?

当然，如果能帮忙将三叶推荐身边的朋友就更好啦 ~