如何用记忆化优化C++斐波那契？自顶向下实现为何超时？

你已经正确实现了斐波那契数列的自底向上DP方案：

int fib(int n) {
    int dp[n + 2];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

但你尝试的两种自顶向下（记忆化）实现均出现超时，核心问题在于递归过程中错误调用了原fib函数，而非复用当前的记忆化数组，导致记忆化完全失效，退化成了时间复杂度为O(2^n)的普通递归。

错误实现的核心问题 #

两种写法里，递归计算时都用了dp[n] = fib(n - 2) + fib(n - 1);：

• 每次调用fib都会重新创建一个新的dp数组，之前缓存的结果完全无法复用
• 相当于重复计算所有子问题，完全没有利用记忆化的优化效果
• 另外，Lambda版本的递归写法还存在编译问题：C++中递归Lambda需要显式用std::function声明类型，否则编译器无法推导递归调用的类型

修复后的实现 #

1. Lambda函数版本

修改递归调用为Lambda自身，同时用std::function解决递归类型推导问题：

int fib(int n) {
    if (n == 0) return 0; // 处理边界，避免创建空vector
    std::vector<int> dp(n + 1, -1);

    // 用std::function显式声明类型，支持递归调用
    std::function<int(int)> recurse = [&](int n) {
        if (dp[n] != -1)
            return dp[n];

        if (n == 0) {
            return dp[n] = 0;
        }
        if (n == 1){
            return dp[n] = 1;
        }
            
        // 调用recurse而非fib，复用同一个dp数组
        dp[n] = recurse(n - 2) + recurse(n - 1);
        return dp[n];
    };

    recurse(n);
    return dp[n];
}

2. 外部递归函数版本

修改递归调用为recurse函数，复用传入的记忆化数组：

int recurse(int n, std::vector<int>& dp) {
    if (dp[n] != -1)
        return dp[n];

    if (n == 0) {
        return dp[n] = 0;
    }
    if (n == 1){
        return dp[n] = 1;
    }
      
    // 调用recurse而非fib，复用传入的dp数组
    dp[n] = recurse(n - 2, dp) + recurse(n - 1, dp);
    return dp[n];
}

int fib(int n) {
    if (n == 0) return 0; // 处理边界，避免创建空vector
    std::vector<int> dp(n + 1, -1);
    recurse(n, dp);
    return dp[n];
}

额外说明 #

修复后的代码时间复杂度为O(n)，空间复杂度为O(n)，和自底向上版本效率一致。如果追求极致空间，也可以将记忆化数组替换为两个变量（和自底向上的空间优化思路一致），但记忆化的核心优势是适配更复杂的子问题依赖场景，斐波那契只是入门案例。

内容的提问来源于stack exchange，提问作者Paul Clauss