# 动态规划神课深读：长记性的暴力 一提动态规划（Dynamic Programming，下称 DP），多数程序员的表情都很复杂：面试绕不开，LeetCode 上带 DP 标签的题有数百道，可真到动手写的时候，脑子里只剩“状态转移方程”六个字在打转。背题的人多，懂原理的人少。今天要安利的这节课，来自 MIT 的算法名课 6.006（Introduction to Algorithms, Fall 2011）第 19 讲，主讲人是 Erik Demaine——据 MIT 公开资料，他 20 岁就加入 MIT 教职，是该校史上最年轻的教授之一。这节课他用一节标准时长的 MIT 大课，只讲了两个例子：斐波那契和最短路径。听起来平平无奇，但它解决了一个困扰无数人的问题：**DP 到底是天赋还是流程？** 答案是后者。这节课把 DP 从“背方程”还原成“设计子问题”，给出了一条任何人都能复制的推导路径。看完你会发现，DP 不是天才的顿悟，而是普通人的流水线。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | MIT 6.006 Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths | | 频道 | MIT OpenCourseWare（官方课程频道） | | 时长 | 约75分钟（MIT标准课时，未精确核实） | | 播放量 | OCW 算法类长期热门课程，被全球高校课堂广泛引用（单视频播放量未精确核实） | | 核心主题 | 用斐波那契与最短路径两个例子，讲透动态规划的本质：递归 + 记忆化 | ## 核心内容拆解 ### 要点一：DP 的第一性定义——“加了记忆的暴力” 视频原话（大意）：动态规划本质上就是 "careful brute force"（小心翼翼的暴力），也可以理解为 "recursion + memoization"（递归加记忆化）。Demaine 开篇就给 DP 祛魅：它不是什么高深的数学结构，底层动作土得掉渣——把所有可能暴力枚举一遍，只是不让计算机重复劳动。理解了这一点，后面所有花哨技巧都是这句话的推论。【延伸分析】这个定义的心理价值被严重低估。它意味着你拿到 DP 题时不需要“灵光一现”：先老老实实写一个正确的暴力递归，剩下的是机械优化。把“想出 DP”降级成“写对暴力、修掉重复”，是这节课给初学者最大的心理松绑——DP 的门槛从来不是智商，而是流程。 ### 要点二：递归树——同一块砖被搬了一万遍 朴素斐波那契：fib(n) = fib(n-1) + fib(n-2)。Demaine 在黑板上画出完整递归树，重复立刻现形：为了算 fib(n)，fib(n-2) 要被算 2 次，fib(n-3) 要被算 3 次，越往树底走，重复越恐怖——像 fib(3) 这样的小子问题，会被从头再算指数多次。复杂度是多少？递归树的节点数按黄金比例 φ≈1.618 的 n 次方增长，即 O(φ^n)，比 2^n 略慢，但同样是天文数字：n=50 时就算到宇宙热寂也算不完。【延伸分析】这一段的真正教益是：“慢”的根源不是计算量大，而是**重复**——真正独立的子问题只有 n 个，计算机却干了指数倍的活。找到重复、消灭重复，这就是全部 DP 的种子。画递归树这个动作本身，就值得变成你的肌肉记忆。 ### 要点三：一行修复——记忆化 修复方式简单到离谱：加一个字典或数组，算过的结果存起来，下次先查表，查到就直接返回。这就是 memoization（记忆化）。代码改动只有几行，复杂度却从 O(φ^n) 直接掉到 O(n)——每个 fib(k) 只真正计算一次，其余全是 O(1) 查表。这是“自顶向下”的 DP：从原问题出发老老实实递归，顺手记住答案。视频原话（大意）：这是把指数复杂度变成线性的“一行修复”。【延伸分析】这个思想在工程里随处可见。任何带重复调用的递归——配置解析、编译器的符号处理、带缓存的渲染计算——都值得先问一句：我的递归树里有多少重复节点？有大量重复，就值得上缓存；没有重复，缓存只是浪费内存。先画树、再判断，这个顺序不能反。 ### 要点四：反过来算——打表与拓扑序 记忆化还有一个进化版：既然每个子问题只依赖更小的子问题，那干脆从最小的开始，按依赖顺序把整张表填满——这就是“自底向上”的 DP 打表。好处有二：没有递归调用的开销，而且更容易压缩空间。斐波那契只依赖前两项，所以根本不用存整张表，滚动保留最后两个变量就够，空间从 O(n) 降到 O(1)。【延伸分析】“按依赖顺序填表”这个说法，在图论里有正式名字：拓扑序。DP 能跑通的前提，是子问题的依赖图必须无环（DAG）。想明白这一点，你就知道为什么有些题“怎么定义状态都死循环”——多半是状态之间存在循环依赖，需要增加一个维度把环打破。这类debug思路，课本很少讲，实战极常用。 ### 要点五：设计子问题才是真功夫 斐波那契只是热身，DP 真正的难点在于“子问题怎么定义”。6.006 这门课把方法论贯穿成一套完整流程，可以压缩成五步：①定义子问题；②做猜测——在局部选择上枚举所有可能；③用子问题的解写出递推关系；④递归加记忆化，或自底向上打表；⑤回到原问题取答案。课程还给出一条万能复杂度公式：总时间 ≈ 子问题个数 × 每个子问题的计算代价。【延伸分析】这条公式是面试时的仪表盘：拿到题先数状态有几个维度、每个维度多大，再估单步代价，复杂度当场脱口而出。面试官问“你的算法多快”，能用这条公式现场推导的人，和背方程的人，一眼就能分出高下。所谓“DP 直觉”，就是这条公式用多了之后的条件反射。 ### 要点六：从斐波那契到最短路——δ_k 递推推出 Bellman-Ford 第二部分是全课最硬核的地方：用同一套框架推导单源最短路径。定义子问题 δ_k(v)：从起点 s 到点 v、最多经过 k 条边的最短路径长度。递推关系是：要么不用第 k 条边（δ_{k-1}(v)），要么枚举最后一条边从哪个前驱 u 走过来（δ_{k-1}(u) + 边权 u→v），两者取最小。让 k 从 1 一路滚到 |V|-1，你就推导出了经典的 Bellman-Ford 算法，复杂度 O(|V|·|E|)，而且天生扛得住负权边——这是 Dijkstra 做不到的。【延伸分析】看懂这个推导，你会发现教科书里的“算法”不过是某个 DP 状态的展开。学算法的顺序因此可以反转：先掌握 DP 框架，再把经典算法当作练习题逐个推一遍，比上来就硬背 Bellman-Ford 的伪代码高效得多。顺带一提，这套方法由 Richard Bellman 在 1950 年代发明，“动态规划”这个名字也是他起的。 ### 要点七：DP 救不了的问题——识别状态的天花板 这节课同样有清晰的边界意识（大意）：子问题之间能画成有向无环图，DP 才成立。最短路径在 DAG 里按拓扑序扫一遍就完事，甚至“最长路径”在 DAG 里也只是把 min 换成 max，同样一遍过；但放到一般图上，最长简单路径是著名的 NP 难问题——不是 DP 公式失灵，而是必须区分的状态数本身就是指数级，“记忆”要记的东西多到记不动。【延伸分析】这给我们的核心直觉是：拿到问题先估状态空间。旅行商问题（TSP）看似无解，但用“当前在哪个城市 + 访问过哪些城市”定义状态，2^n × n² 的表虽然指数，n=20 时依然可算——这叫“可控的指数”；而一般图最长路连这样的表都定义不出来。会区分这两种情况，比会默写十个模板更有价值。知道 DP 什么时候失效，才算真的懂 DP。 ## 知识结构图 ```mermaid flowchart TD A["一道题，暴力要算到天荒地老"] --> B["画出递归树"] B --> C["发现同一子问题算了几十遍"] C --> D["第一步：定义子问题"] D --> E["第二步：猜，枚举局部选择"] E --> F["第三步：写递推关系"] F --> G["第四步：记忆化或打表"] G --> H["每个子问题只算一次"] H --> I["指数降到多项式"] D --> J["总耗时=子问题数×单步代价"] I --> K["斐波那契：指数变线性"] I --> L["最短路：推出贝尔曼-福特"] I --> M["DAG最长路：拓扑序一遍过"] ``` ## 实战启示 **面试党：把流程焊死在手上。** 下次遇到任何 DP 题，严格走五步：先写最笨但正确的暴力递归；画出递归树找重复节点；加个字典变记忆化；需要优化空间或被追问时改打表；最后用“子问题数 × 单步代价”报出复杂度。这套流程的价值在于它不依赖题感——哪怕从没见过的题，你也能在一个结构里稳定产出解。线性 DP、背包、最长公共子序列这些题族，不过是同一流程在不同状态定义上的重复练习。 **工程师：缓存之前先查依赖图。** 记忆化不是万能药，它的前提是子问题依赖图无环。在工程里给递归逻辑加缓存之前，先确认两件事：一是有没有真实的重复计算（没有重复就别浪费内存），二是依赖关系能不能排成一个无环的顺序。另外“滚动变量”的思路也值得偷师——很多场景不需要保存全量历史，只留最近一两个状态就够了，内存立刻从 O(n) 降到 O(1)。 **所有人：早识别天花板，及时止损。** 这节课最重要的隐性技能，是让你在动手前先估状态空间。如果必须区分的状态数本身是指数级且压不下来（如一般图最长路），就别在 DP 上死磕，赶紧换思路或接受近似解。这个“第一眼判断能不能算”的能力，在面试和真实工程里都极其值钱——它决定你是花二十分钟写出解，还是花两天写出一个跑不动的解。 ## 延伸学习路径 1. **同课程第 20–22 讲**（MIT OCW 免费观看）：文本对齐、矩阵链乘、编辑距离、背包问题，最后一讲甚至用 DP 玩俄罗斯方块和超级马里奥——是“五步法”的连续实战。 2. **NeetCode 的 Dynamic Programming 题单**（YouTube/网站免费）：按题族刷 DP 的最佳路径，与 6.006 的方法论完美互补。 3. **《Competitive Programmer's Handbook》**（Antti Laaksonen，免费 PDF）：竞赛视角的 DP 章节，状态设计技巧更密集。 4. **CLRS《算法导论》DP 章节**：作为工具书查阅，把课上口算的递推式对照严谨证明过一遍。 5. **强化学习中的 Bellman 方程**：同一套递推思想在另一个领域的重生——学完这节课再去看 RL，会有强烈的“原来是他”之感。 ## 一句话总结 动态规划不是玄学，是给暴力搜索装上记忆：先数清楚子问题，再让每个子问题只算一次——指数到多项式的距离，只隔着一个“记性”。 ## 参考来源 1. [MIT 6.006 Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths](https://www.youtube.com/watch?v=OQ5jsbhAv_M) — 本文分析的核心视频（MIT OpenCourseWare 官方频道；如链接有变动，在 YouTube 搜索完整标题可直达） 2. [MIT OCW 6.006 Introduction to Algorithms, Fall 2011 课程主页](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/) — 全部讲义、习题与视频 3. [Competitive Programmer's Handbook（免费 PDF）](https://cses.fi/book/book.pdf) — 竞赛视角的 DP 系统补充 4. [Introduction to Dynamic Programming（cp-algorithms）](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html) — 可交互的 DP 入门与模板库 --- > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。