本讲定位：动态规划系列的第一讲，也是最重要的一讲。我们不直接背”状态转移方程”，而是回答一个更根本的问题：DP 到底是从哪里来的？ 学完本讲你会发现：DP 不是一种新算法，而是”递归 + 不做重复计算”的自然结果。
前置知识：函数与递归的基本写法、二维数组。
适合对象：CSP-J 及以上。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。
斐波那契数列的定义大家都熟悉：
$$ F_1 = F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \ (n \ge 3) $$
定义本身就是递归式的，所以我们很自然地写出递归程序：
long long fib(int n) {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
这份代码正确，但你如果实际运行 fib(50)，会发现它要跑上几十秒。为什么？
我们把 fib(6) 的调用过程画成一棵树：
fib(6)
/ \
fib(5) fib(4)
/ \ / \
fib(4) fib(3) fib(3) fib(2)
/ \ / \ / \
fib(3) fib(2) fib(2) fib(1) fib(2) fib(1)
/ \
fib(2) fib(1)
数一数：fib(4) 被完整地计算了 2 次，fib(3) 被计算了 3 次，fib(2) 被计算了 5 次……同一个问题被反反复复地重算，这就是重叠子问题。
这棵调用树的结点个数本身就按斐波那契数列的速度增长，时间复杂度约为 $O(1.618^n)$——指数级。$n = 50$ 时大约要做 $10^{10}$ 次运算，自然慢得离谱。
关键观察：
fib(4)不管被谁调用、什么时候调用，答案永远是 3。既然答案不变，为什么要算两遍？
改进的思路非常朴素：开一个数组当”笔记本”，每个子问题第一次算完就把答案记下来，之后再被问到，直接翻笔记。
long long f[105]; // f[n] 记录 fib(n) 的答案，0 表示还没算过
long long fib(int n) {
if (n <= 2) return 1;
if (f[n] != 0) return f[n]; // 算过了，直接查表返回
return f[n] = fib(n - 1) + fib(n - 2); // 没算过，算完顺手记下来
}
只加了两行，效果却是质变的：每个 fib(i) 只会被完整计算一次，之后的调用都是 $O(1)$ 的查表。时间复杂度从 $O(1.618^n)$ 降到了 $O(n)$。
这个技巧叫做记忆化搜索（memoization）。它的适用条件只有一个：