记忆化搜索CSP-S

💡 核心思想

记忆化搜索是在递归搜索的基础上，将已计算过的子问题结果缓存起来，避免重复计算。本质上是动态规划的自顶向下实现方式。通常能把指数级复杂度优化为多项式级。

🎯 直觉理解

想象你在解一棵很大的递归树。没有记忆化的话，同样的子问题会被算很多很多次。记忆化就像你在草稿纸上记录："$f(5)=120$，算过了别再算了"。下次遇到 $f(5)$ 直接查表。

📝 算法流程

1. 写出朴素的递归搜索
2. 添加备忘录（数组或map）存储已计算结果
3. 递归入口先查表：算过直接返回
4. 没算过则递归计算，存入备忘录后返回

$$\text{朴素斐波那契: } O(2^n) \to \text{记忆化: } O(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
long long memo[1005];
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // 查表
    return memo[n] = fib(n-1) + fib(n-2); // 计算+存储
}
int main() {
    memset(memo, -1, sizeof(memo));
    int n; cin >> n;
    cout << fib(n) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目