# 五小时拆墙：动态规划的万能骨架 ## 导语：被恐惧放大的算法关卡 如果你在程序员群体里做个调查，“你最怕的算法主题”里动态规划（Dynamic Programming，简称 DP）大概率稳居前三。它承载了太多传说：面试刷人利器、天赋测试器、“看题解都会，合上题解就废”。可讽刺的是，这个让无数人劝退的主题，核心思想用一句话就能说完：**把算过的东西记下来，别算第二遍**。 这轮要深读的，是 freeCodeCamp 频道上累计播放数百万次的算法长课《Dynamic Programming - Learn to Solve Algorithmic Problems & Master Recursion》。讲师 Alvin（算法练习平台 Structy 的作者）用约 5 个小时，只讲了一个动作：**画递归调用树**。整门课像做手术一样，把这个传说中最难的主题，拆成了“画树 → 递归实现 → 加缓存剪枝”三步可复制的流程。它解决的核心问题只有一个：动态规划不是灵光一现的天赋题，而是一套可以刻意练习的模式识别。这不是又一门“刷题大全”，而是一门“解题操作系统”安装课。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | Dynamic Programming - Learn to Solve Algorithmic Problems & Master Recursion | | 频道 | freeCodeCamp.org（订阅量千万级的公益编程教育频道） | | 讲师 | Alvin（算法练习平台 Structy 作者） | | 发布时间 | 2021 年 | | 时长 | 约 5 小时 | | 播放量 | 累计数百万（据 YouTube 公开页面，长期位居 freeCodeCamp 算法类课程前列） | | 核心主题 | 用“递归树 + 缓存 + 填表”三件套系统通关动态规划 | ## 核心内容拆解 ### 1. 先拆掉心墙：DP 到底难在哪 课程开篇，Alvin 给动态规划下了一个极简定义：**DP = 递归 + 缓存**。他强调，DP 难的原因不是数学，而是没人教你“看见”递归如何展开。整个课程的方法论由此定调：拿到任何问题，先把它的递归结构**画成一棵树**，树画对了，代码只是翻译。（视频原话与课程立意） **延伸分析**：这个定位非常诚实。市面上多数教程直接甩“状态转移方程”，等于让你背公理；而这门课先建立几何直觉，再谈公式。认知科学里这叫从“程序性记忆”入手——先会做，再理解，恰好和算法教学的普遍失败模式相反。 ### 2. 从 fib 看指数爆炸是怎么发生的 课程从最朴素的斐波那契递归开始：`fib(n) = fib(n-1) + fib(n-2)`。Alvin 现场画出了这行代码的调用树——树每往下一层，节点数近乎翻倍。他逐层数给你看：算 `fib(50)`，树上有约 2 的 50 次方量级的节点，也就是千万亿次函数调用，而其中绝大多数是在**重复计算同几个数字**。（视频核心演示） **延伸分析**：这一节的价值在于把“重叠子问题”（overlapping subproblems）这个抽象名词变成看得见的形状：树上同一批节点被抄写了成千上万遍。DP 的全部收益都来自一个朴素动作——同一道子题，只算一次。 ### 3. Memoization：给递归装上缓存 接下来是全场第一个“ magic 时刻”：在递归函数里加一个 JS 对象当备忘录——算过的结果存进去，每次递归先查表，查到就直接返回。还是那棵树，只是重复的子树被整枝剪掉，`fib(50)` 从千万亿次调用骤降到约 n 次线性级别。Alvin 把这套流程总结成课程里反复出现的口诀：**make it work, then make it efficient**——先让暴力递归跑对，再无脑加缓存变快。（视频核心方法论） **延伸分析**：值得点破的是，memoization 就是缓存（caching）在算法里的样子。你写 React 时的 `useMemo`、写后端时的 Redis 缓存、数据库的查询缓存，和这里加的那行 `if (n in memo) return memo[n]`，是同一个思想的不同方言。 ### 4. gridTraveler：证明骨架可以迁移 第二个问题：一个 m×n 的网格，从左上角只能向右或向下走，走到右下角有几种走法？Alvin 用同样的画树法拆解：每一步两个分支（向右/向下），坐标不断缩小，直到边界。加缓存时他顺手演示了一个经典剪枝：`gridTraveler(m, n)` 和 `gridTraveler(n, m)` 是同一道子题，把 `(1,3)` 和 `(3,1)` 视为同一个 key，缓存命中率立刻翻倍。（视频演示） **延伸分析**：这一节是全课的转折点——你会发现 fib 和 gridTraveler 完全不同的故事背后是**完全相同的树形**。这就是“DP 面试题换皮不换骨”的第一次实证。它对应的正是 LeetCode 62 题 Unique Paths，难度中等，但在骨架面前只是换个坐标说话。 ### 5. canSum / howSum / bestSum：三胞胎看穿题型分层 课程中段最精彩的设计：同一组原料（一个目标数 targetSum、一个数字数组 numbers，可重复使用，问能否恰好凑出），Alvin 连做三题——`canSum` 只回答能否（返回布尔），`howSum` 返回任意一个组合（返回数组），`bestSum` 返回最短组合（返回最优解）。三个函数共用同一棵递归树，只在返回值上做文章。加上缓存后，复杂度从指数级压到“目标值 × 选项数”的多项式量级。（视频核心设计） **延伸分析**：这个“三胞胎”其实是把面试题的三大问法（判定型、构造型、优化型）一次性拆穿了。背题的人会把“零钱兑换”当新题，而理解骨架的人一眼看出它是 `bestSum` 换了个硬币皮肤——对应 LeetCode 322。 ### 6. construct 家族：字符串上的同一棵树 课程随后把同样的骨架搬进字符串世界：给定目标字符串和词表，`canConstruct` 问能否拼出，`countConstruct` 问有几种拼法，`allConstruct` 列出全部拼法。画树的方式从“数字缩小”变成“前缀剥掉”，但递归结构、缓存写法、复杂度分析，全部照旧。（视频演示） **延伸分析**：这一族对应 LeetCode 139/140（Word Break I/II），是 DP 题里伪装性最强的类型——很多人栽在这里是因为只见过数字版 DP。这门课把数字、网格、字符串三种皮肤各过一遍，等于给“模式识别”上了三重保险。这也是我认为它比多数 DP 课更值得推荐的根本原因。 ### 7. 通用配方：全课真正想让你背走的流程 如果要给 5 个小时提炼成一张流程卡，就是课程反复演练的这条：**第一，把问题画成树**——确认“每一步有哪些分支”和“什么算到底”（base case）；**第二，把树翻译成递归代码**——此时它很慢但正确；**第三，找出树上的重复子树**——给递归函数加上由参数唯一确定的 memo key；**第四，分析复杂度**——时间等于“子问题个数 × 每个问题的合并成本”。（视频方法论总结） **延伸分析**：注意一个容易被忽略的点：memo 的 key 必须由**全部参数**唯一决定。字符串题要拼 `head + ',' + tail`，网格题要用 `(m,n)` 有序对——key 设计错了，缓存就会“污染”。这个细节无数教程不讲，却是实际写代码时最常见的翻车点。 ### 8. Tabulation：把递归倒过来写的自底向上 课程后半段引入了 DP 的另一副面孔：**tabulation（打表法）**。以 fib 为例——不写递归，先建一张长度 n+1 的表，`table[i]` 表示“f(i) 的答案”，从 `table[1] = 1` 出发，用一个 for 循环把整张表从左往右填满。gridTraveler 也被改写成一张二维表逐格累加。Alvin 对比了两种风格：memoization 是自顶向下的“拆问题”，tabulation 是自底向上的“攒答案”。（视频后半场主线） **延伸分析**：工程视角下 tabulation 常更受欢迎——没有递归就没有栈深度限制（长输入下递归版可能爆栈），常数更小，而且状态之间只依赖前几项时还能把表压缩成几个变量，把空间从 O(n) 降到 O(1)。面试里的高分答法往往是：先用画树+memo 快速拿到正确解，再顺势改成 table 展示工程素养——恰好就是这门课的教学顺序。 ## 知识结构图 ```mermaid flowchart TD A["动态规划 DP = 递归 + 缓存"] --> B["第一步：画递归调用树"] A --> C["关键前提：重叠子问题"] B --> D["朴素递归：指数级爆炸"] C --> E["Memoization 自顶向下"] D --> E E --> F["数量型：fib 与 gridTraveler"] E --> G["判定与构造：canSum howSum bestSum"] E --> H["字符串型：canConstruct 家族"] G --> I["同一棵树，三种返回值"] H --> I E --> J["Tabulation 自底向上"] J --> K["先建表再迭代填表"] K --> L["复杂度：指数级降为多项式"] ``` ## 实战启示 看完这门课，你能带走一套可以直接执行的训练方案： **第一，按课程的顺序打三周。** 第一周只练“画树”：fib、gridTraveler、canSum，每题先在纸上画完调用树再写代码；第二周过 canSum/bestSum 和 construct 两大家族，要求自己说出每题是“判定、构造、优化”里的哪一种；第三周学 tabulation，把 memo 版逐题改写成 table 版。每天 1-2 题，一个月后 DP 对你不再是玄学。 **第二，面试时把思考过程外化。** 这门课示范的画树动作，本身就是最好的面试话术：先讲暴力递归（证明你能拆问题），再指出重叠子树（证明你懂 DP），最后加 memo 并报复杂度（证明你懂工程）。面试官要的从来不是“秒出状态转移方程”，而是这条可追溯的推理链。 **第三，把骨架映射到题库。** LeetCode 70（爬楼梯）≈ fib，62（Unique Paths）≈ gridTraveler，322（零钱兑换）≈ bestSum，139/140（Word Break）≈ construct 家族。做完课程后去这些题上验证迁移能力，会获得极强的正反馈。 **第四，迁移到工程里。** memoization 就是缓存，tabulation 就是迭代填表——理解了这对孪生思想，你在做接口缓存、动态规划式资源配置、甚至 React 性能优化时，手里多了一套有名字的心智模型，而不是零散的技巧。 ## 延伸学习路径 1. **Structy**（structy.net）— 讲师 Alvin 自己的算法练习平台，课程同款题目体系，配套代码可以逐题验证。 2. **CP-Algorithms《Intro to Dynamic Programming》**（cp-algorithms.com）— 进入进阶阶段的免费文字教程，覆盖背包、LIS 等经典模型。 3. **MIT 6.006《Introduction to Algorithms》**（MIT OpenCourseWare，ocw.mit.edu）— 想从工程直觉升级到理论证明，看大学正版的 DP 讲授。 4. **GeeksforGeeks Dynamic Programming 专题**（geeksforgeeks.org/dynamic-programming/）— 题型索引式的参考手册，适合当字典查。 5. **LeetCode 动态规划标签页**（leetcode.com/tag/dynamic-programming/）— 按频次刷本课骨架对应的真题，检验迁移效果。 ## 一句话总结 这门 5 小时的课证明了一件事：**动态规划从不考验天赋，它只考验你愿不愿意先画一棵树——画对了树，剩下的只是给递归加一行缓存。** ## 参考来源 1. [Dynamic Programming - Learn to Solve Algorithmic Problems & Master Recursion — freeCodeCamp](https://www.youtube.com/watch?v=oBt53YbR9Kk) — 本文分析的核心视频 2. [Structy — 讲师 Alvin 的算法练习平台](https://structy.net) — 课程配套题库 3. [CP-Algorithms: Intro to Dynamic Programming](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html) — 进阶理论补充 4. [MIT 6.006 Introduction to Algorithms (Spring 2020)](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/) — 学院派 DP 讲授 5. [LeetCode: Dynamic Programming 标签](https://leetcode.com/tag/dynamic-programming/) — 骨架迁移的真题演练场 --- > 本文由「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 等场景全覆盖。