记忆化搜索CSP-S

💡 核心思想

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

🎯 直觉理解

记忆化搜索就是给递归"记笔记"：同一个子问题算过一遍，就把结果存下来，下次直接查表，不再重复算。

以斐波那契为例：朴素递归算 $f(40)$ 要重复算 $f(30)$ 几千次；加一个数组缓存，每个值只算一次，复杂度从 $O(2^n)$ 降到 $O(n)$。

记忆化搜索 = 递归 + 缓存，本质是"自顶向下"的动态规划。写法上只要：函数加一个记录数组，算之前先查、算完就存。它比递推版 DP 更好写，因为状态转移方向自然。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include 
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;
}

⚠️ 常见坑点

📚 相关题目