如果你只在教科书上见过“最优子结构、无后效性、状态转移方程”这套黑话，却从没亲手把一个跑不完的指数级递归救活成秒出的线性算法，那么这条接近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万+（约数，未经二次核实） |
| 核心主题 | 用“记忆化 + 制表法”两板斧，从零系统拆解动态规划 |
课程开场不讲任何定义。Alvin 直接写下最朴素的斐波那契递归：fib(n) = fib(n-1) + fib(n-2)，然后调用 fib(50)——页面卡住，久等不出。他把递归树画在白板上：每个节点分裂成两个子节点，50层下去，调用量约在2的50次方这个量级，也就是百万亿次级的函数调用。
但把这棵树画出来一看，真相就藏不住了：fib(47)、fib(46)、fib(45)……同样的子问题在树的不同枝干上反复出现，一遍一遍重算。课程里反复传达的核心信息是：指数爆炸的根源不是递归本身，而是重复子问题。只要把算过的结果存起来，整棵指数级的树会“坍缩”成一条线性链。
我的延伸：这个开场设计非常高明。很多人怕DP，怕的是“状态转移方程”这种数学外衣；而这里把问题还原成了一个性能事故现场——你不是在学数学，你是在修一个跑不动的程序。心态先就赢了一半。
全课程前半段（记忆化/Memoization部分）其实就在教一套固定动作，Alvin 每遇到新题都完整重演一遍，大致可以概括为四步（步骤划分是我的归纳，内容出自课程）：
这套流程的关键洞察在于：memo 的 key 就是“会变化的那个输入”。fib 里是 n，后面二维问题里就是 (m,n) 组合。课程反复强调：能跑的暴力解是前提，账本是加速器——反过来先背“状态转移方程”的人，往往连暴力解都写不出来。
我的延伸：这套“先正确、再高效”的次序，其实可以迁移到几乎所有性能优化工作：先写一个正确但慢的参照实现，它既是调试基准，也是优化后的正确性验证工具。这一步很多工程师会跳过，然后在自己的“优化”里翻车。
第二道例题换了个画风：在一个 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的一半功力不在转移，而在你选什么作为子问题的坐标。面试里很多人卡住，不是不会递归，是没想清楚“状态里该装哪些信息、装少了答错、装多了爆炸”。
课程中段是含金量最高的“三连问”系列，同一个题干，问法逐级加码：给定 targetSum 和一个可重复使用的数字数组——
canSum(7, [5,3,4]) 为 true（3+4）。布尔型子问题，账本记 true/false；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（零钱兑换）的完整原型，而“负例也要缓存”在工程里对应的是缓存空值/缓存穿透防护——把“查过了、没有”和“没查过”区分开，是所有缓存系统的基本功。
后半程把数字题整体平移到字符串：给定 target 和一个词库 wordBank（词可重复使用），问 target 能否由词库中的词拼接而成——这是 canConstruct；追问有几种拼法，是 countConstruct；要求列出全部拼法，是 allConstruct。
结构上它和 canSum 完全同构：子问题从“剩余的目标值”换成“target 的前缀/后缀切片”，选择从“减去某个数”换成“匹配某个词”，账本的 key 从数字换成字符串切片。课程用这种刻意的“换皮重复”，向你灌输它最想教的元认知：DP 题目千变万化，骨架只有一副——识别状态、定义选择、递归到底、回填账本。
我的延伸：这个字符串骨架在真实系统里到处都是——分词器的最大匹配、拼写检查、LeetCode 139 Word Break，本质都是 canConstruct。学DP最重要的收获不是会做题，而是获得一种眼力：看到“把大串/大数拆成子串/子数”的需求，能立刻反应出这是一棵可以记账的树。
课程最后引入第二板斧：自底向上的制表法（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" 指的是规划、调度这类优化活动，和“写代码”无关。所以“动态规划”其实是“动态决策的规划方法”——一个为立项而生的营销名，最终成了整个算法王国的正式户口。这段往事流传甚广，出自当事人自述，学界常引，细节以原书为准。
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 一行装饰器，感受指数到线性的坍塌。另外记住课程埋的那条工程铁律——负例也是结果，缓存“不存在”和没缓存是两回事，这一条能帮你挡掉大多数缓存穿透事故。
方法论层面的迁移：整门课最有长期价值的其实是那八个字——先让它工作，再让它高效。保留一个朴素正确的参照实现，再谈优化；优化完拿大输入验证。这套纪律用在数据库调优、正则改写、并发改造上，同样成立。
动态规划的全部秘密，不过是给每个子问题发一本账——先让暴力递归跑通，再把算过的每一笔都记下来，指数的雪崩就塌缩成一张安安静静的表。
本文由「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 等场景全覆盖。