# 动态规划神课：指数爆炸终结者——把一条数百万播放的算法课拆开看 ## 一、概述：这条视频为什么值得读 在程序员的集体噩梦排行榜上，“动态规划”（Dynamic Programming，下文简称 DP）常年霸榜：概念抽象、题型千变、面试必考。而 freeCodeCamp 频道的这条《Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges》（《动态规划——学习解决算法问题与编程挑战》），是 YouTube 上被引用、被推荐最多的 DP 系统课之一，由讲师 Alvin Zablan 主讲，时长约 5 小时，从最简单的斐波那契一路讲到字符串组合爆炸问题，全程手画递归树，把“指数爆炸如何被一把剪刀剪成线性”演给你看。 这条视频的价值不只是“面试突击材料”。它实际上完成了一次完整的思维示范：**同一个问题，在暴力递归、记忆化、自底向上表格法三种形态下如何逐步变形**。这个“变形记”本身，就是计算机科学里“用空间换时间”这一元思想最清晰的实物教材。本文按视频叙事顺序拆解其核心内容，追溯背后的真实理论源流，并对其中的主张做一轮批判性审查。 > 数据说明：本篇撰写环境无法联网实时核验，播放量、发布日期等动态数据请以 YouTube 频道页面为准，文中仅给出公开资料中长期稳定的量级描述，不做精确编造。 ## 二、视频基本信息 | 项目 | 内容 | |------|------| | 视频标题 | Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges（动态规划——学习解决算法问题与编程挑战） | | 频道 | freeCodeCamp.org（开源教育 charity 运营的大型编程教学频道，订阅数为千万量级） | | 讲师 | Alvin Zablan（后创办算法学习平台 Structy） | | 发布时间 | 2020 年（据频道页面，精确日期请以页面为准） | | 时长 | 约 5 小时的完整课程 | | 播放量 | 数百万量级，为其频道内算法类长课程的头部作品（以频道页面实时数据为准） | | 形式 | 白板/画布手绘递归树 + JavaScript 代码演示，零框架依赖 | ## 三、核心主张拆解：按视频叙事顺序 ### 要点一：开场即暴击——斐波那契的递归树 视频不从定义入手，而是直接写一个最朴素的递归 `fib(n) = fib(n-1) + fib(n-2)`，然后画出调用树。以一个十几规模的输入为例，树迅速膨胀：每个节点分叉两个子节点，深度为 n。讲师现场数节点，得出结论：这棵树的节点数量是 **O(2ⁿ)** 量级——输入每加 1，计算量翻倍。`fib(50)` 在这台机器上跑到天荒地老。 这是全片的方法论锚点：**性能问题不是抽象数字，而是一棵你亲眼看着长歪的树**。讲师反复强调的手绘习惯，是整门课最重要的“肌肉记忆”——后面每一个优化，都是在这棵树上动剪刀。 ### 要点二：记忆化三步法——画树、找重叠、加缓存 剪第一刀的地方，是树上那些**长一模一样的子树**：`fib(5)` 会被算两次，`fib(3)` 会被算更多次。这些重复出现的子问题，就是“重叠子问题”（overlapping subproblems）。讲师给出的操作口诀非常具体： 1. **画树**：把暴力递归的调用树画出来； 2. **找重叠**：圈出重复出现的节点（参数相同的子问题）； 3. **加缓存**：用一个哈希表（JS 里的对象/Map）把算过的结果存起来，下次遇到直接查表返回。 改动只有几行，复杂度却从 O(2ⁿ) 塌缩到 **O(n)**——树不再分叉，而是一条链。这个“给递归加备忘录”的技术就叫记忆化（memoization）。视频用 `fib(50)` 瞬间出结果作为戏剧性收尾，让观众第一次直观感受到缓存的力量。 ### 要点三：二维升级——网格旅行者问题 接下来把方法论从一维推向二维：`gridTraveler(m,n)`，问一个 m×n 的网格里，从左上角只能向右或向下走，到右下角有几种走法。这道题的价值在于演示**状态（子问题）的选取**：每走一步，问题就变成“在剩余的 (m-1,n) 或 (m,n-1) 网格里走”，子问题的参数从 1 个变成 2 个，缓存表的键也从单个数字变成坐标对。 不优化时复杂度是 O(2^(m+n))，加记忆化后降到 **O(m·n)**。这一节回答了一个初学者最常见的困惑：“DP 的缓存表到底该怎么定义？”讲师的答案是：表的维度等于“描述一个子问题所需的变量个数”——这句话几乎是全片含金量最高的一句口诀。 ### 要点四：决策题族三连——canSum、howSum、bestSum 课程的第三幕是一组层层加码的“目标求和”问题，这是全片最精彩的部分，因为它演示了**同一道题的三种问法如何对应三种难度**： - **canSum(target, numbers)**：能否用数组里的数字（可重复使用）凑出 target？返回布尔值。暴力是指数级，加缓存后 O(target × numbers.length)； - **howSum**：不光要判断，还要返回一种具体的凑法。难度上调，因为缓存的值从布尔变成了数组，且失败路径要显式返回 null 才能正确剪枝； - **bestSum**：要返回数字个数最少（或按题意最优）的那种凑法。缓存命中条件更严格——只有“更优解”才值得覆写缓存。 这一组题把“判断题 → 构造题 → 最优化题”的难度阶梯讲透了。面试中的大量 DP 题，本质上都在这个阶梯上滑动，而这正是 DP 的经典形态之一：**最优化原理**——最优解的余部，仍是余部问题的最优解。 ### 要点五：字符串战场——Construct 三兄弟与组合爆炸 第四幕把数字换成字符串：`canConstruct(target, wordBank)`（能否用词表拼出目标词）、`countConstruct`（有几种拼法）、`allConstruct`（返回所有拼法）。这里出现了全片最震撼的可视化：当求解 `allConstruct` 的某个用例时，返回结果的规模本身就会指数级膨胀——**你就算把计算优化到极致，答案本身就有天文数字个**。 讲师没有回避这一点，反而把它变成教学点：遇到这类问题，先问“输出规模有多大”。如果答案本身是指数级的，任何算法都不可能快——这不是你的代码烂，是问题定义使然。这种“认清问题边界”的判断力，比任何套路都稀缺。 ### 要点六：自底向上——Tabulation 表格法 课程的最后一幕补上另一半版图：自底向上（bottom-up）的表格法。不再从 `fib(n)` 往下递归，而是从最小子问题开始，把答案逐格填进一张表，每个格子的答案由更小的格子拼出来。它的优势：没有递归调用栈（不会栈溢出）、缓存局部性好、常常可以把表格压缩成几个滚动变量，把空间从 O(n) 压到 O(1)。 至此，视频完成了方法论闭环：**先写暴力递归（定义问题）→ 画树找重叠（识别 DP）→ 加缓存（记忆化/top-down）→ 翻成表格（tabulation/bottom-up）**。四个阶段不是四道孤立的题型，而是同一思想的四种物理形态。 ## 四、知识与理论溯源 视频本身几乎不谈历史，但它讲的每一步都有扎实的学术源头，值得逐一挂接： **1. 动态规划的诞生：贝尔曼与兰德公司。** DP 由数学家 Richard Bellman 在 1950 年代于美国兰德公司（RAND Corporation）工作时提出，系统论述见于他 1957 年出版的专著《Dynamic Programming》。关于这个古怪的名字，贝尔曼在自传《Eye of the Hurricane》（1984）中留有名场面的回忆：当时的国防部长威尔逊对基础研究态度敌视，他担心“数学”“研究”这类词会招致预算砍杀，于是选了"dynamic"——既描述了问题的多阶段时变特性，又听起来气势磅礴、无法被国会否定。这段轶事真假细节虽有史家讨论，但出自贝尔曼本人的白纸黑字，是 DP 史上被引用最多的段子。 **2. 两个成立条件。** 教科书（Cormen 等人的《算法导论》CLRS，第 15 章）给出 DP 适用性的经典判据：**重叠子问题**（overlapping subproblems）与**最优子结构**（optimal substructure）。视频里“圈出重复节点”圈的就是前者，“bestSum 的最优解由子最优解拼成”演示的就是后者。视频没点名这两个术语，但其全部例题都在为这两个判据提供实物样本。 **3. “记忆化”一词的来源。** memoization 由人工智能先驱 Donald Michie 在 1968 年发表于《Nature》的论文《Memo Functions and Machine Learning》中提出，本意就是把函数的“备忘录”存下来——这个词与 generalization（泛化）对举，是他早期机器学习思想的一部分。它与"memorization"（死记硬背）无词源关系，这也是面试里的一道冷知识题。 **4. 惊人的谱系。** 视频里那道网格旅行者题，往上数是 1202 年斐波那契《Liber Abaci》里兔子问题的直系后代；bestSum 所代表的最优化形态，衍生出贝尔曼方程、1967 年 Viterbi 算法（通信与 CDMA 之父 Viterbi 提出，今天仍在 4G/5G 信道译码里运行）、1962 年的 Floyd–Warshall 最短路算法；字符串那几道题的近亲，是 1970 年 Needleman–Wunsch 的生物序列比对，以及你每天都在用的 `git diff` 背后的 LCS（最长公共子序列）思想。换句话说：**这条 YouTube 视频教的，是一门从 1950 年代一路铺到 5G 芯片和代码仓库里的看家手艺。** ## 五、批判性审查 **证据充分的部分。** 视频的复杂度分析全部可以在纸面复核：递归树计数、缓存命中后的复杂度坍缩，与 CLRS 等主流教材完全一致。记忆化带来的指数级到多项式级的收益，属于算法领域最没有争议的结论之一。这部分内容读者可以放心吸收。 **需要打折扣的部分。** 其一，视频用 JavaScript 演示，且大量依赖递归——在 Python/Java 等语言里默认递归深度受限，照抄会栈溢出，这正是实践中人们更偏爱自底向上表格法的原因之一，视频对此着墨偏少。其二，“学完这 5 小时就能拿下 DP”的隐性承诺要谨慎对待：DP 题型空间极大（区间 DP、树形 DP、状态压缩 DP、数位 DP 等进阶形态并未覆盖），这门课是极好的“第一性原理课”，但不是完备的题库。其三，记忆化以空间换时间，缓存的键空间可能随输入维度爆炸——真实工程里还需要滚动数组、惰性求值等进一步压缩手段，视频基本没有展开。 **存在争议的部分。** 这类课程是“算法面试军备竞赛”文化的产物。围绕“用 DP 刷题筛选工程师是否合理”，工程社区（如 Hacker News 上历年反复出现的长帖）存在长期争论：批评方认为这筛选的是应试模式识别能力而非工程能力；支持方认为“把模糊问题归约为清晰子问题”恰恰是核心工程素养。这个争论没有定论，但它提醒我们：把这门课当作**思维体操**来学，价值坚实；把它当作**求职保命符**来背，则可能南辕北辙——真正的面试高区分度题，恰恰会设计成“背过的套路失灵”的样子。 ## 六、认知提升与实用启示 **启示一：遇到递归超时，先画树再动手。** 可操作的流程：把递归调用画成树 → 圈出参数完全相同的节点 → 有重复，就上一张哈希表（Python 里一行 `@functools.lru_cache` 即可）。这个“先诊断、后优化”的动作，能把 80% 的“递归好慢”问题在十分钟内定位。 **启茧二：用两个问题自检 DP 适用性。** 动手写 DP 前，先问：“描述一个子问题需要哪几个变量？”（决定缓存表的维度）；“大问题的最优解，能否由某个子问题的最优解拼接而来？”（最优子结构）。两个问题都有肯定答案，放心 DP；有一个答不上来，考虑贪心、搜索或换状态定义。 **启示三：按“四段式”建立自己的解题流水线。** 拿到任何新题：先写暴力递归并验证小用例（获得正确性基准）→ 加缓存（获得可接受性能）→ 视需要翻成表格（规避栈深度、提升缓存友好）→ 视内存约束压缩状态。这条流水线既是面试策略，也是真实工程里处理组合爆炸问题的标准作业程序——从拼写纠错到通信系统的 Viterbi 译码，骨架完全相同。 ## 七、一张图看懂视频的论证结构 ```mermaid flowchart TD A["斐波那契递归树
复杂度 O(2^n)"] -->|"圈出重复节点"| B["记忆化缓存
坍缩到 O(n)"] B --> C["记忆化三步法
画树 找重叠 加缓存"] C --> D["二维升级
网格旅行者 O(m·n)"] D --> E["决策题族
canSum 到 bestSum"] E --> F["字符串题族
Construct 三兄弟"] F --> G["认清边界
答案本身可能爆炸"] G --> H["自底向上 Tabulation
表格法收束方法论"] H --> I["四段式流水线
暴力 缓存 表格 压缩"] ``` ## 延伸阅读 1. **MIT 6.006《Introduction to Algorithms》动态规划讲次**（Erik Demaine、Jason Ku、Justin Solomon 等主讲，MIT OpenCourseWare）——把本视频的直觉版内容，翻译成带严格证明的大学版本，两者对照食用效果最佳。 2. **Richard Bellman《Dynamic Programming》（1957）及自传《Eye of the Hurricane》（1984）**——前者是 DP 的开山之作，后者收录了“dynamic”这个名词诞生的名场面，理解一个术语背后的科学政治学。 ## 参考来源 > 注：本篇撰写环境无法联网实时抓取，以下为长期稳定的公认来源链接，动态数据（播放量等）请以页面实时显示为准。 1. [Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges — freeCodeCamp.org](https://www.youtube.com/watch?v=oBt53YbR9Kk) — 本文解读对象，Alvin Zablan 主讲的 DP 完整课程 2. [Dynamic programming - Wikipedia](https://en.wikipedia.org/wiki/Dynamic_programming) — 贝尔曼命名轶事、最优性原理与理论脉络 3. [Memoization - Wikipedia](https://en.wikipedia.org/wiki/Memoization) — 记忆化术语的来源（Michie 1968） 4. [6.006 Introduction to Algorithms — MIT OpenCourseWare](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/) — 动态规划讲次的学院派对照版本 --- > 本文由「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 等场景全覆盖。