降低C++中类斐波那契递归爬楼梯函数的时间复杂度

优化思路 #

你当前代码的性能问题来源于暴力递归存在大量重复计算，时间复杂度为指数级的O(3^n)，n稍微大一点就会出现超时。我们可以通过**记忆化递归（备忘录递归）**优化，完全满足仅使用递归的要求，优化后时间复杂度降到O(n)，可以轻松处理大数值n。

优化逻辑是额外开辟一块存储空间，记录已经计算过的n对应的方案数，后续再遇到相同的n时直接读取缓存结果，无需重复递归计算。

注意事项 #

• 你需要把返回值类型从int改为long long，因为取模数值10000000007已经超过了32位int的最大值，用int存储会出现溢出错误。
• 记忆化缓存可以用全局数组、静态变量，或者作为参数传入递归函数均可。

优化后代码示例 #

const long long MOD = 10000000007LL;
// memo数组用来缓存已计算的结果，初始值设为-1表示未计算
long long memo[1000010]; // 可以根据需要调整数组大小，这里假设n最大为1e6

long long ways(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;
    // 已经计算过的结果直接返回
    if(memo[n] != -1) return memo[n];
    // 计算结果存入缓存再返回
    memo[n] = (ways(n-3) + ways(n-2) + ways(n-1)) % MOD;
    return memo[n];
}

// 调用前需要先初始化memo数组，比如在main函数里执行memset(memo, -1, sizeof(memo));

补充说明 #

如果需要处理的n极大（比如超过1e6），O(n)复杂度的记忆化递归也无法满足要求，可以采用递归实现的矩阵快速幂方法，时间复杂度可以进一步降到O(logn)，哪怕n达到1e18量级也可以快速计算出结果。

内容的提问来源于stack exchange，提问作者Yash Yadav