记忆化搜索

记忆化搜索 = 递归的写法 + 一个数组存已算过的答案。它保留了搜索"照着定义直接写"的直观，又靠缓存拿到了 DP 的速度。做法：额外开一个 $memo$ 数组，进函数先查缓存，命中就直接返回，没算过才递归、算完存进去。要多准备的就是这个缓存数组，外加一个"尚未计算"的标记值（比如 $-1$）。

long long memo[100005];
long long f(int i) {
    if (i <= 1) return 1;
    if (memo[i] != -1) return memo[i];   // 命中缓存
    return memo[i] = f(i-1) + f(i-2);    // 算完顺手存下
}
// 调用前：memset(memo, -1, sizeof(memo));

每个状态只真正计算一次，复杂度和递推 DP 一样是 $O(n)$。它的好处是不用操心递推顺序——想算谁就调谁，依赖关系由递归自动理顺，特别适合转移顺序不好确定的题（树上 DP、区间 DP）。坑：标记值别和真实答案撞车（若答案可能是 $-1$，就换个不可能的标记）；递归太深可能爆栈，深度大时改用递推。