# 动态规划神课：别让递归白算 ## 概述 在 YouTube 的编程教学区，有一条被无数程序员称为“动态规划救命课”的超长视频：freeCodeCamp 频道发布、讲师 Alvin 主讲的《Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges》。它没有炫酷特效，就是一块白板加一支笔，用五个多小时把“动态规划”这个让无数人面试折戟的题目，拆成了人人能跟上的画图课。本文逐段拆解这条视频的论证路线，讲清它背后的真实理论与工业落地，也指出哪些地方需要打折扣来听。没看过视频，你能看懂全部核心内容；看过视频，你能多懂一层。 ## 一、视频基本信息 | 项目 | 内容 | |------|------| | 视频标题 | Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges | | 中文对照 | 动态规划——学会解决算法问题与编程挑战 | | 频道 | freeCodeCamp.org（公益编程教育频道，千万级订阅） | | 讲师 | Alvin（Alvin the Programmatic Programmer） | | 发布时间 | 2020年10月 | | 时长 | 约5小时17分 | | 播放热度 | 近千万量级，长期位列该频道最热门算法教程之列（据频道页面，本轮未实时核验） | | 语言 | 英文，YouTube 免费观看 | | 链接 | https://www.youtube.com/watch?v=oBt53YbR9Kk | > 注：本轮页面实时抓取受限，表中数据为据频道页面的历史信息，精确数值请以视频页为准。 ## 二、这条视频讲了什么：五步登顶路线 Alvin 的整堂课其实只反复证明一件事：**动态规划 = 递归 + 记忆**。但为了让这句话真正长进听众脑子里，他设计了一条极其讲究的登山路，五段路程，一步比一步陡。 ### 第一步：用 fib(50) 的灾难开场 视频不从定义开始，而是直接算 Fibonacci 数列第 50 项。裸递归一行写完，漂亮极了，然后 Alvin 画出了它的调用树：求 fib(50) 要展开成 fib(49) 和 fib(48)，再各自展开……树越画越大，最后他点破：这棵树的时间复杂度是指数级 O(2^n)，宇宙热寂了你也算不完。更扎心的是让听众看树里反复出现的节点——fib(48) 被算了两遍，fib(47) 被算了三遍，越往下重复越密集。**问题不在递归，在于同样的子问题被反复重算。** 解药也随之而来：准备一个大字典（JavaScript 里就是对象或 Map），每次算出答案先记下来，下次遇到同一问题直接查表。这一个“加缓存”的动作，让复杂度从指数坍缩到线性。这就是记忆化（memoization）。 ### 第二步：gridTraveler，学会“翻译问题” 第二个例子是一个走网格问题：m×n 的棋盘，从左上角走到右下角，每次只能右移或下移，问有几种走法。这一步教的是 DP 最难也最不被言说的技能——**把一个人话描述的问题，翻译成一个带参数的函数签名**。Alvin 给出的诀窍是：网格缩小就变成子问题，参数 (m, n) 就是状态。他故意用 (1,1)、(2,3) 这类小例子验证，让你亲眼看到“边界条件”是怎么从画图里自然长出来的，而不是背出来的。 ### 第三步：canSum 三连，函数签名才是真功夫 这是全课的精华段。同一个背景——给你一组数字，能不能凑出目标值——被演成三集连续剧： - **canSum**：能不能凑出来？返回布尔值。 - **howSum**：能的话，给出任意一种凑法？返回数组。 - **bestSum**：给出用数字最少的那种凑法？返回最优数组。 三集的代码骨架几乎一样，但 Alvin 用它们逼你直面两个关键点：一是“移动目标”（move the target）——每一层递归里，目标和在变，剩余数字不变，所以函数签名里谁是状态、谁是常量，直接决定你的记忆化是否有效；二是返回值类型变了（布尔、数组、最优数组），缓存的合并逻辑就完全不同，bestSum 甚至要小心数组拷贝带来的额外开销。很多自学 DP 的人卡壳，不是不懂递归，而是从没系统练过“如何设计状态”——这三集就是补这一课的。 ### 第四步：canConstruct，字符串世界的同一场戏 接下来把数字换成字符串：能否用给定的词表拼出目标单词（canConstruct）、有几种拼法（countConstruct）、所有拼法都是什么（allConstruct）。套路与前一段完全同构，但字符串带来了新坑：拼接是有顺序的，切前缀还是切后缀，决定了会不会漏解、重解。Alvin 在这里反复让听众自己先画、再写、最后他对答案——整条视频的教学法就是“可视化优先”：先在白板上画出树，看清重复，再动手编码。 ### 第五步：tabulation，掉头向下的另一条路 最后一段，Alvin 掉转方向讲自底向上：不递归了，直接开一张表格，从最小的子问题填起，一路填到答案。这就是 tabulation。它和 memoization 算的是同样的东西，但省掉了函数调用栈，天然没有栈溢出的风险，也更贴近机器的执行方式。视频以斐波那契和走网格的表格版收尾，完成了“自顶向下”与“自底向上”的合流。 ## 三、知识与理论溯源 ### 贝尔曼与那个“故意起错的名字” 动态规划不是互联网时代的面试发明，它诞生于 1950 年代的兰德公司（RAND Corporation）。创立者理查德·贝尔曼（Richard Bellman）在 1984 年的自传《Eye of the Hurricane》里留下了一段著名自白：当时的美国国防部长查尔斯·威尔逊极度反感“研究”这个词，贝尔曼为了让自己的数学研究继续拿到经费，刻意挑了一个无法被攻击的名字——"dynamic"（动态）既指问题随时间变化，又因为这个词“不可能被用在贬义语境”；而"programming"在当时指“规划、调度”（与丹齐格的线性规划同族），跟写代码毫无关系。也就是说，这个吓退了无数学生的术语，一半是数学，一半是职场生存智慧。 ### 原理的最小表述 教科书（以 CLRS《算法导论》为代表）把 DP 适用条件收敛为两条：**重叠子问题**（overlapping subproblems，同样的子问题会被反复遇到）和**最优子结构**（optimal substructure，大问题的最优解由子问题的最优解构成）。贝尔曼 1957 年的专著《Dynamic Programming》里将其表述为著名的“最优性原理”：无论初始状态和初始决策如何，余下的决策必须对第一个决策所产生的状态构成最优策略。视频里 Alvin 的“画树找重复”，本质上就是用肉眼去检验第一条；他反复强调的函数签名设计，检验的是第二条。 顺便修正一个视频里为了教学简化的数字：裸递归斐波那契的严格上界不是 O(2^n) 而是 O(φ^n)，φ≈1.618（黄金比例），因为每层只展开一个分支到底。但这不改变结论——它依然是指数级，记忆化之后依然是线性。 ### 从 diff 到基因：DP 的两次工业落地 动态规划绝不是“面试专用知识”，它至少两次深刻改变了工业世界。 第一次在软件工具链。Unix 的 `diff` 命令核心是 Hunt 与 McIlroy 1976 年在贝尔实验室提出的算法，基于最长公共子序列（LCS）——一个教科书级 DP 问题。今天你每天 `git diff` 看到的代码差异，用的是 Eugene Myers 1986 年提出的 O(ND) 差分算法，同样是 DP 思路的产物。你每次提交代码前瞄一眼的红色绿色，背后都是那张“填表”。 第二次在生物信息学。1970 年 Needleman 与 Wunsch 在《Journal of Molecular Biology》发表全局序列比对算法，1981 年 Smith 与 Waterman 发表局部比对算法——两者都是标准 DP，把两条 DNA 链的比对问题变成一张二维打分表的填表过程。人类基因组计划的比对工具谱系里，这两支 DP 算法是直接祖先。此外，拼写检查依赖的编辑距离（Levenshtein 1965 年提出，Wagner–Fischer 1974 年给出经典 DP 实现）、语音识别早期的动态时间规整（DTW，Sakoe 与 Chiba 1978）、路由算法中的 Floyd–Warshall 全源最短路（1962），全都在这张族谱上。 ## 四、批判性审查：哪些可信，哪些要打折 **证据充分的部分**：视频的全部算法内容——递归树分析、记忆化的写法、复杂度结论、自底向上填表——与 CLRS、MIT OCW 6.006 等标准教材完全一致，且每一步都有可视化验证，属于“可自己动手复算”的知识，可信度极高。Alvin 的“画树 → 找重复 → 设计签名 → 加缓存”方法论，也被广泛认为是入门 DP 最平缓的路径之一。 **需要打折扣的部分**有三处。 其一，**“加缓存就快”有前提**。视频淡化了状态数量的核心地位：记忆化的复杂度等于“状态数 × 每个状态的转移成本”，如果状态本身是指数级的，缓存救不了你。经典的旅行商问题用 Held–Karp 型 DP 是 O(n²·2ⁿ)，城市数到二十几个就到头了，工业求解器转头去用启发式算法。看完视频容易产生“万物皆可 DP”的错觉，实际工程里先数状态再动手。 其二，**生产环境要警惕深递归**。视频用 JavaScript 演示自顶向下，但多数运行时对深递归并不友好：Python 默认递归上限约一千层，浏览器里的 JS 调用栈通常也只有几万帧，目标值取十万级时 memo 版会直接爆栈。这时 tabulation 不是“另一种风格”，而是唯一稳健的选择——视频虽然讲了 tabulation，但对这层动机强调不足。 其三，**这是“面试 DP”，不是 DP 全景**。五个小时覆盖的是面试高频子集（线性/二维网格/背包型构造问题），概率 DP、位运算 DP 的高级玩法、斜率优化等竞赛向内容基本不涉及。对面试者恰到好处，对算法竞赛选手只是起点。另外，围绕“背模板还是懂原理”的路线之争在编程社区（如 r/learnprogramming、LeetCode 讨论区）长期存在，据社区讨论，支持理解派的会推荐这条视频，模板派则嫌它太长——五小时单一讲师的体量，确实不是人人都啃得动，这一点视频本身无法替你解决。 ## 五、认知提升与实用启示 **第一，用“两问法”识别 DP 问题。** 拿到任何问题先问两句：能不能表述为“每步做一个决策”（可行/最值/方案数）？决策之后，剩下的部分是不是“一个更小的同类问题”？两问都是“是”，再画一棵小规模的递归树，看树里有没有重复节点。重复出现了，才值得上记忆化；没有重复，DP 是多余的弯路。 **第二，写代码遵守“三步走”，别一步登天。** 先写最笨的暴力递归——它就是你正确性的基准；然后机械地加 memo，只改三处：签名加缓存参数、函数入口查缓存、返回前写缓存；确认正确后，若有爆栈或性能需求，再翻写成 tabulation。一上来就填表的人最容易在状态定义上翻车，因为跳过了“树长什么样”这个最重要的直觉来源。 **第三，把“备忘录”当成一种通用工程观。** 这条视频教的其实是一种超越算法的思维：凡是会重复发生的计算，都值得被记住答案。工程世界里满地都是它的变体——React 的 `useMemo` 记住组件计算的中间值，Turborepo 和 sccache 记住上次构建的产物，数据库的物化视图记住聚合查询的结果，CDN 记住边缘节点的响应。下次你给系统加缓存时，你做的正是 Alvin 在白板上做的同一个动作：认出重复，然后拒绝重算。 ## 六、一图看懂：这条视频的论证结构 ```mermaid flowchart TD A["fib(50) 裸递归慢如龟"] --> B["画出调用树"] B --> C["发现重复子问题"] C --> D["加备忘录：空间换时间"] D --> E["指数坍缩为线性"] E --> F["gridTraveler 练翻译"] F --> G["canSum 三连练签名"] G --> H["canConstruct 同款戏"] H --> I["tabulation 填表法"] I --> J["方法论：先画树再写码"] J --> K["迁移：缓存皆备忘录"] ``` ## 延伸阅读 1. MIT OCW 6.006《算法导论》（2020 春季学期）Dynamic Programming 单元——Erik Demaine 主讲，与本文视频互为"理论版/实操版"：https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ 2. Wikipedia: Dynamic programming 词条——贝尔曼命名轶事、最优性原理与各领域应用的总览入口：https://en.wikipedia.org/wiki/Dynamic_programming ## 参考来源 1. [Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges](https://www.youtube.com/watch?v=oBt53YbR9Kk) — freeCodeCamp.org，本文解读对象（数据据频道页面，未实时核验） 2. [Dynamic programming - Wikipedia](https://en.wikipedia.org/wiki/Dynamic_programming) — 贝尔曼、最优性原理与应用谱系 3. [MIT OCW 6.006 Introduction to Algorithms, Spring 2020](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/) — DP 单元课程与讲义 4. R. Bellman, *Eye of the Hurricane: An Autobiography* (1984) — "dynamic programming" 命名轶事原始出处（书籍） 5. J. Hunt, M. McIlroy, *An Algorithm for Differential File Comparison* (Bell Labs, 1976) — Unix diff 的 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 等场景全覆盖。