一提动态规划（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 算法类长期热门课程，被全球高校课堂广泛引用（单视频播放量未精确核实） |
| 核心主题 | 用斐波那契与最短路径两个例子，讲透动态规划的本质：递归 + 记忆化 |
视频原话（大意）：动态规划本质上就是 "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(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 才成立。最短路径在 DAG 里按拓扑序扫一遍就完事，甚至“最长路径”在 DAG 里也只是把 min 换成 max，同样一遍过；但放到一般图上，最长简单路径是著名的 NP 难问题——不是 DP 公式失灵，而是必须区分的状态数本身就是指数级，“记忆”要记的东西多到记不动。【延伸分析】这给我们的核心直觉是：拿到问题先估状态空间。旅行商问题（TSP）看似无解，但用“当前在哪个城市 + 访问过哪些城市”定义状态，2^n × n² 的表虽然指数，n=20 时依然可算——这叫“可控的指数”；而一般图最长路连这样的表都定义不出来。会区分这两种情况，比会默写十个模板更有价值。知道 DP 什么时候失效，才算真的懂 DP。
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 上死磕，赶紧换思路或接受近似解。这个“第一眼判断能不能算”的能力，在面试和真实工程里都极其值钱——它决定你是花二十分钟写出解，还是花两天写出一个跑不动的解。
动态规划不是玄学，是给暴力搜索装上记忆：先数清楚子问题，再让每个子问题只算一次——指数到多项式的距离，只隔着一个“记性”。
本文由「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 等场景全覆盖。