内容摘要
动态规划 · 把大问题拆成小问题 灏 灏天文库 · 算法与数学基础 第 2 期 · 连载中 算法与数学基础 · 第 2 期 动态规划：把大问题 拆成小问题 记忆化 vs 递推 · dynamic programming step-by-step 算 fib(40) 暴力递归要算 约 1 亿次 ，动态规划只算 40 次 。差别不在算法聪明，而在 重复的子问题只算一次 。DP 的本质是给递归加一张表，把指数级的重复计算压成线性。 ⏱ 约 10 分钟 🎯 知道递归但没听过 DP 的人 📦 源：OI-wiki · DP 入门 01 一个反共识：DP 不是新算法，是递归加张表 很多人觉得动态规划很玄，其实它就是"递归 + 记忆化"。同一个子问题第二次被问到时，直接查表返回，不再往下递归。 fib(n) = fib(n−1) + fib(n−2) 暴力递归算 fib(5) 时，fib(2) 被算了 3 次，fib(3) 被算了 2 次。n 一大，重复呈树形爆炸——fib(40) 的递归树有约 1.65 亿个节点，其中 fib(2) 一个就被算了约 3900 万次。