在程序员的集体噩梦排行榜上，“动态规划”（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）。讲师给出的操作口诀非常具体：
改动只有几行，复杂度却从 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 的缓存表到底该怎么定义？”讲师的答案是：表的维度等于“描述一个子问题所需的变量个数”——这句话几乎是全片含金量最高的一句口诀。
课程的第三幕是一组层层加码的“目标求和”问题，这是全片最精彩的部分，因为它演示了同一道题的三种问法如何对应三种难度：
这一组题把“判断题 → 构造题 → 最优化题”的难度阶梯讲透了。面试中的大量 DP 题，本质上都在这个阶梯上滑动，而这正是 DP 的经典形态之一：最优化原理——最优解的余部，仍是余部问题的最优解。
第四幕把数字换成字符串：canConstruct(target, wordBank)（能否用词表拼出目标词）、countConstruct（有几种拼法）、allConstruct（返回所有拼法）。这里出现了全片最震撼的可视化：当求解 allConstruct 的某个用例时，返回结果的规模本身就会指数级膨胀——你就算把计算优化到极致，答案本身就有天文数字个。
讲师没有回避这一点，反而把它变成教学点：遇到这类问题，先问“输出规模有多大”。如果答案本身是指数级的，任何算法都不可能快——这不是你的代码烂，是问题定义使然。这种“认清问题边界”的判断力，比任何套路都稀缺。
课程的最后一幕补上另一半版图：自底向上（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 译码，骨架完全相同。
flowchart TD
A["斐波那契递归树<br/>复杂度 O(2^n)"] -->|"圈出重复节点"| B["记忆化缓存<br/>坍缩到 O(n)"]
B --> C["记忆化三步法<br/>画树 找重叠 加缓存"]
C --> D["二维升级<br/>网格旅行者 O(m·n)"]
D --> E["决策题族<br/>canSum 到 bestSum"]
E --> F["字符串题族<br/>Construct 三兄弟"]
F --> G["认清边界<br/>答案本身可能爆炸"]
G --> H["自底向上 Tabulation<br/>表格法收束方法论"]
H --> I["四段式流水线<br/>暴力 缓存 表格 压缩"]
注：本篇撰写环境无法联网实时抓取，以下为长期稳定的公认来源链接，动态数据（播放量等）请以页面实时显示为准。
本文由「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 等场景全覆盖。