记忆化搜索

上一课的 f(n)=f(n-1)+f(n-2) 如果直接写成递归，会慢得离谱——因为同一个 f(k) 被算了无数遍。

慢在哪

算 f(5) 要算 f(4) 和 f(3)；算 f(4) 又要算 f(3) 和 f(2)……f(3) 被重复算了好几次。规模一大，重复次数呈指数级爆炸。

记忆化：算过就存

开一个数组 memo[] 当备忘录，每个状态只算一次，之后直接取：

int memo[MAXN];                       // 初值 -1 表示"还没算过"
int f(int n){
    if(n<=2) return n;                // 边界
    if(memo[n]!=-1) return memo[n];   // 算过就直接用
    return memo[n] = f(n-1)+f(n-2);   // 算完顺手存下来
}

这就是"递归 + 备忘录"。它把指数级的暴力递归降到了 $O(n)$：每个状态只被真正计算一次。记忆化搜索是理解 DP 最自然的入口——你只要照着递归式写，再加一行"存 / 取"。