爬楼梯DP算法中数组初始化位置引发超时的原因咨询

在求解爬楼梯动态规划问题时，发现将dp数组定义在climbStairs函数内部会触发超时（TLE），但将其定义为类的成员变量时，代码就能被系统接受。以下是对应代码：

超时代码 #

class Solution {
public:
    
    int climbStairs(int n) {
        
        int dp[46];      
        if(dp[n]!=0) return dp[n]; 
        if(n==1 ||n==2) return n;
        dp[n]=climbStairs(n-1)+climbStairs(n-2);
        return dp[n];
    }
};

通过代码 #

class Solution {
public:
    int dp[46];
    int climbStairs(int n) {
        
        if(dp[n]!=0) return dp[n]; 
        if(n==1 ||n==2) return n;
        dp[n]=climbStairs(n-1)+climbStairs(n-2);
        return dp[n];
    }
};

核心原因分析 #

• 局部dp数组的本质问题：
  每次调用climbStairs函数时，都会在栈上创建一个全新的dp数组，这个数组的初始值是随机垃圾值，并非默认0。更关键的是，每个递归调用的dp数组都是独立的——你以为在缓存结果，但实际上每次递归都在用新数组，之前计算的结果根本存不住，等于退化成了纯暴力递归，时间复杂度是O(2ⁿ)，当n增大时必然超时。同时，dp[n]!=0的判断完全不可靠，可能返回随机的垃圾值，进一步破坏逻辑。

• 类成员dp数组的作用：
  类成员变量的dp数组属于Solution类的实例，只会初始化一次（全局/类成员变量默认初始化为0），所有递归调用共享同一个数组。第一次计算出dp[n]的值后，后续再遇到相同n时，直接返回缓存的结果，真正实现了记忆化搜索，时间复杂度降到O(n)，满足题目时间限制。

哪怕你把局部dp数组手动初始化为0，依然会超时——因为每个递归栈帧的dp还是独立的，无法共享缓存结果，还是会重复计算所有子问题。

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