## 一个让百万人入门动态规划的“笨办法” 如果你只在教科书上见过“最优子结构、无后效性、状态转移方程”这套黑话，却从没亲手把一个跑不完的指数级递归救活成秒出的线性算法，那么这条接近5小时的视频，可能是你在YouTube上能找到的最友好的动态规划（Dynamic Programming，下称DP）完整课。它没有炫技，没有堆术语，甚至开局故意写一个“卡死浏览器”的烂代码给你看——然后再用一句朴素的口诀，一步一步把它救回来。 这条视频在编程圈的江湖地位很特殊：它常年霸榜 freeCodeCamp 算法类视频的头部（播放量800万+量级，约数，未经二次核实），评论区高频词不是“讲得好”，而是“我终于懂了”。讲师 Alvin Zablan 是面试刷题平台 Structy 的创始人，他在这门课里反复强调的次序只有八个字：**先让它工作，再让它高效**。这句话本身就是对DP最好的祛魅——DP不是玄学，是记账。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges | | 频道 | freeCodeCamp.org（全球最大的免费编程教学频道之一） | | 讲师 | Alvin Zablan（Structy 创始人） | | 发布时间 | 2020年10月 | | 时长 | 约5小时 | | 播放量 | 800万+（约数，未经二次核实） | | 核心主题 | 用“记忆化 + 制表法”两板斧，从零系统拆解动态规划 | ## 核心内容拆解 ### 一、fib(50)卡死的那几十秒：指数爆炸的真凶是“重复” 课程开场不讲任何定义。Alvin 直接写下最朴素的斐波那契递归：`fib(n) = fib(n-1) + fib(n-2)`，然后调用 `fib(50)`——页面卡住，久等不出。他把递归树画在白板上：每个节点分裂成两个子节点，50层下去，调用量约在2的50次方这个量级，也就是百万亿次级的函数调用。 但把这棵树画出来一看，真相就藏不住了：`fib(47)`、`fib(46)`、`fib(45)`……同样的子问题在树的不同枝干上反复出现，一遍一遍重算。课程里反复传达的核心信息是：**指数爆炸的根源不是递归本身，而是重复子问题**。只要把算过的结果存起来，整棵指数级的树会“坍缩”成一条线性链。 我的延伸：这个开场设计非常高明。很多人怕DP，怕的是“状态转移方程”这种数学外衣；而这里把问题还原成了一个性能事故现场——你不是在学数学，你是在修一个跑不动的程序。心态先就赢了一半。 ### 二、记忆化配方：四步流水线，像菜谱一样照做 全课程前半段（记忆化/Memoization部分）其实就在教一套固定动作，Alvin 每遇到新题都完整重演一遍，大致可以概括为四步（步骤划分是我的归纳，内容出自课程）： 1. **画树**：把问题的“当前状态”画成节点，把“每一步的选择”画成边，递归到不能递归的地方就是叶子，也就是 base case； 2. **翻译成递归代码**：树怎么画，代码就怎么写，先别管性能； 3. **加 memo**：准备一个字典作账本，函数入口先查账（查到直接返回），算完、返回之前先记账； 4. **换个大输入验证**：比如把 n 从 20 拉到 50，肉眼可见地从“卡死”变“秒出”。 这套流程的关键洞察在于：**memo 的 key 就是“会变化的那个输入”**。fib 里是 n，后面二维问题里就是 (m,n) 组合。课程反复强调：能跑的暴力解是前提，账本是加速器——反过来先背“状态转移方程”的人，往往连暴力解都写不出来。 我的延伸：这套“先正确、再高效”的次序，其实可以迁移到几乎所有性能优化工作：先写一个正确但慢的参照实现，它既是调试基准，也是优化后的正确性验证工具。这一步很多工程师会跳过，然后在自己的“优化”里翻车。 ### 三、gridTraveler：二维状态与“key的艺术” 第二道例题换了个画风：在一个 m×n 的网格里，从左上角走到右下角，每步只能向右或向下，问有多少种走法。base case 很直觉：1×1 的格子只有1种走法；任何一边为0，走法为0。 暴力递归下，`gridTraveler(18,18)` 又跑不动了；加账本之后秒出答案：**2333606220，23亿多种走法**。这道题教了两个教科书级的技巧。第一，二维状态怎么当 key——把 m 和 n 串成一个字符串 `"m,n"`（或将二元组作为 key），一个数装不下，就拼一个复合键。第二，课程顺带点出对称性：从 18×18 走和从“转置后”的网格走是等价的，`(a,b)` 和 `(b,a)` 可以共用一条账目，账本还能再省一半。 我的延伸：这一题其实是在教“状态设计”——DP的一半功力不在转移，而在你选什么作为子问题的坐标。面试里很多人卡住，不是不会递归，是没想清楚“状态里该装哪些信息、装少了答错、装多了爆炸”。 ### 四、canSum / howSum / bestSum：同一棵树的三种问法 课程中段是含金量最高的“三连问”系列，同一个题干，问法逐级加码：给定 targetSum 和一个可重复使用的数字数组—— - **canSum**：能否恰好拼出 target？如 `canSum(7, [5,3,4])` 为 true（3+4）。布尔型子问题，账本记 true/false； - **howSum**：返回任意一种拼法组合。答案从布尔升级为路径； - **bestSum**：返回**最短**的拼法组合，如 `bestSum(8, [1,4,5])` 返回 `[4,4]` 而不是 `[1,1,1,1,4]`。答案升级为最优路径。 这一组的精彩之处在于复杂度演变的演示。以 canSum 为例，暴力解是指数级（约为 n 的 m 次方，n是数字个数、m是目标值），加账本后掉回多项式级；而 bestSum 因为要比较、要拷贝数组，每步还多付一份代价——课程把这笔账算得明明白白。还有一个容易被忽略的细节被课程重点强调：**负例也要记账**。像 `canSum(300, [7,14])` 这种答案为 false 的输入， false 同样是昂贵算出的结果，不记下来等于白算。 我的延伸：这三连问就是 LeetCode 322 Coin Change（零钱兑换）的完整原型，而“负例也要缓存”在工程里对应的是**缓存空值/缓存穿透防护**——把“查过了、没有”和“没查过”区分开，是所有缓存系统的基本功。 ### 五、canConstruct 家族：把同一套骨架平移到字符串 后半程把数字题整体平移到字符串：给定 target 和一个词库 wordBank（词可重复使用），问 target 能否由词库中的词拼接而成——这是 **canConstruct**；追问有几种拼法，是 **countConstruct**；要求列出全部拼法，是 **allConstruct**。 结构上它和 canSum 完全同构：子问题从“剩余的目标值”换成“target 的前缀/后缀切片”，选择从“减去某个数”换成“匹配某个词”，账本的 key 从数字换成字符串切片。课程用这种刻意的“换皮重复”，向你灌输它最想教的元认知：**DP 题目千变万化，骨架只有一副**——识别状态、定义选择、递归到底、回填账本。 我的延伸：这个字符串骨架在真实系统里到处都是——分词器的最大匹配、拼写检查、LeetCode 139 Word Break，本质都是 canConstruct。学DP最重要的收获不是会做题，而是获得一种眼力：看到“把大串/大数拆成子串/子数”的需求，能立刻反应出这是一棵可以记账的树。 ### 六、Tabulation 制表法：换个方向填同一张表 课程最后引入第二板斧：**自底向上的制表法（Tabulation）**。以 fib 为例：开一张 n+1 大小的表，先填种子答案（表[0]=0，表[1]=1），然后按顺序向前遍历，把当前格的答案“广播”到它影响的后继格，填到最后一格即是答案。canSum 同理：开一张 target+1 的布尔表，表[0]=true 为种子，逐格向右传递。 为什么同一个问题要学两套写法？课程给出的理由很工程化：递归再优雅，也受调用栈深度的物理约束，输入一大就可能栈溢出；自底向上没有递归，只有一层循环加一张表，性能和内存都更可控。 我的延伸补充（课程以 JavaScript 演示，这一点以 Python 为例更直观）：Python 默认递归深度只有约1000层，`fib` 写成递归+memo 输入几千就会 RecursionError，而制表法毫无压力。从抽象角度看，两条路走的是**同一张依赖图（DAG）**：记忆化是“按需计算、用到才算”，制表法是“全量预计算、按拓扑序填表”。理解了这一点，你就理解了缓存预热、惰性求值、物化视图这些工程概念为什么长得都像DP。 ### 七、复杂度账本：一张表看清优化幅度 课程每道题都做严格的复杂度分析，这里汇总成一张表（口径以课程讲义为准，n 泛指输入规模之一、m 泛指另一规模）： | 题目 | 暴力递归 | 加记忆化后 | 备注 | |------|---------|-----------|------| | fib | O(2ⁿ) | O(n) | 每个子问题只算一次 | | gridTraveler | O(2^(m+n)) | O(m·n) | 复合 key 是关键 | | canSum | O(n^m) | O(m·n) | false 也要记账 | | bestSum | O(n^m · m) | O(m²·n) | 多出的 m 是数组拷贝代价 | 我的延伸：不用死记这张表，记一个直觉就够——**记忆化的本质是把“指数”压成“状态总数 × 单个状态的转移成本”**。看到任何DP题，先问自己两件事：状态有几个？每个状态要做多少次转移？乘起来就是优化后的量级。这个思维模板比任何“万能状态转移方程”都可靠。 ### 八、为什么叫“动态规划”？（延伸阅读，非视频内容） 最后补充一段课程没讲、但知道后会会心一笑的历史。动态规划由数学家 Richard Bellman 在20世纪50年代提出。据 Bellman 本人在自传 *Eye of the Hurricane* 中的自述，他当时在军方资助的研究机构工作，为了让项目名听起来不那么“学究”、避免资助方对数学研究的反感，他刻意挑了听上去有气势的 "dynamic"，而当年的 "programming" 指的是规划、调度这类优化活动，和“写代码”无关。所以“动态规划”其实是“动态决策的规划方法”——一个为立项而生的营销名，最终成了整个算法王国的正式户口。这段往事流传甚广，出自当事人自述，学界常引，细节以原书为准。 ## 知识结构图 ```mermaid flowchart TD ROOT["动态规划：重活只干一次"] --> TOP["自顶向下：记忆化"] ROOT --> BOT["自底向上：制表法"] TOP --> S1["画树定结构"] TOP --> S2["写暴力递归"] TOP --> S3["加memo记账本"] S3 --> S4["大输入验证提速"] BOT --> B1["按输入定表尺寸"] BOT --> B2["填种子答案"] BOT --> B3["按序向右广播"] ROOT --> LAD["课程问题阶梯"] LAD --> P1["fib 一维状态"] LAD --> P2["gridTraveler 二维"] LAD --> P3["canSum 可行性"] LAD --> P4["bestSum 最优解"] LAD --> P5["canConstruct 拆词"] ``` ## 实战启示 **面试党的最短路径**：这门课的题目几乎是 LeetCode 经典题的“教学版母本”——70 Climbing Stairs 就是 fib；62 Unique Paths 就是 gridTraveler；322 Coin Change 就是 bestSum 一族；139 Word Break 就是 canConstruct。最划算的刷法是照课程顺序把这几道题各写两遍：第一遍递归+memo，第二遍 tabulation，写完对照复杂度表自查。约5小时的课消化成十几个小时的上机，性价比远高于题海。 **工程师的账本思维**：memo 不只是算法技巧，它就是缓存的数学原型。前端组件的 memo 化、后端接口的幂等缓存、数据库的物化视图，全是“算过就记账”这同一个思想在不同层的投影。Python 用户今天就能验证这门课的价值：给任何纯函数递归加上 `@functools.lru_cache` 一行装饰器，感受指数到线性的坍塌。另外记住课程埋的那条工程铁律——**负例也是结果**，缓存“不存在”和没缓存是两回事，这一条能帮你挡掉大多数缓存穿透事故。 **方法论层面的迁移**：整门课最有长期价值的其实是那八个字——先让它工作，再让它高效。保留一个朴素正确的参照实现，再谈优化；优化完拿大输入验证。这套纪律用在数据库调优、正则改写、并发改造上，同样成立。 ## 延伸学习路径 1. **Graph Algorithms for Technical Interviews**（freeCodeCamp，同讲师 Alvin Zablan，频道内搜索标题即可）——同样的配方讲图算法，BFS/DFS 一步步画树，与本课构成刷题双璧。 2. **MIT 6.006 Introduction to Algorithms**（[MIT OpenCourseWare](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/)）——学院派对DP的严格表述：最短路径、编辑距离、闭包，适合看完本课后补理论。 3. **CSES Problem Set**（[cses.fi/problemset](https://cses.fi/problemset/)）——DP 专项刷题场，从 Dice Combinations 到 Projects，难度平滑，代码量小、反馈快。 4. **Structy**（[structy.net](https://structy.net/)）——本课讲师的结构化刷题平台，题目顺序与课程脉络一致，适合要系统训练的读者。 5. **Richard Bellman, *Eye of the Hurricane***（World Scientific, 1984）——“动态规划”命名的第一手叙述，一段有趣的科学史花絮。 ## 一句话总结 动态规划的全部秘密，不过是给每个子问题发一本账——先让暴力递归跑通，再把算过的每一笔都记下来，指数的雪崩就塌缩成一张安安静静的表。 ## 参考来源 1. [Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges](https://www.youtube.com/watch?v=oBt53YbR9Kk) — 本文分析的核心视频（freeCodeCamp 频道） 2. [MIT 6.006 Introduction to Algorithms (Spring 2020)](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/) — DP 的学院派补充 3. [CSES Problem Set](https://cses.fi/problemset/) — DP 专项练习题库 4. [Structy](https://structy.net/) — 讲师 Alvin Zablan 的结构化刷题平台 5. Richard Bellman, *Eye of the Hurricane*, World Scientific, 1984 — “动态规划”命名往事的当事人自述 --- > 本文由「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 等场景全覆盖。