LeetCode 70爬楼梯问题数组记忆化搜索出现超时原因求助

• 核心错误是你在重载的带记忆化数组的climbStairs方法中，递归调用的是无dp参数的公有方法，没有用到你创建的记忆数组，相当于每次递归都会重新初始化一个新的Integer数组，之前的记忆结果完全没有复用，本质还是O(2ⁿ)时间复杂度的暴力递归，n较大时必然触发超时。
• 具体出问题的代码行是int step1=climbStairs(n-2);、int step2=climbStairs(n-1);，这里调用的是不带dp参数的版本，而非你写的private的带记忆化逻辑的重载方法。

把递归调用的地方改成传入当前的dp数组即可，修改后的可运行代码如下：

class Solution {
    
    public int climbStairs(int n) {
        if(n<3) return n;
        Integer[] dp= new Integer[n+1];
        return climbStairs(n,dp);
    }
    
    private int climbStairs(int n,Integer[]dp){
        if(n<3) return n;
        if(dp[n]!=null) return dp[n];
        
        int step1=climbStairs(n-2, dp);
        int step2=climbStairs(n-1, dp);
        dp[n]=step1+step2;
        return dp[n];
    }
}

修改后你创建的dp数组会在整个递归链路中复用，每个n对应的结果只会计算一次，时间复杂度降到O(n)，可正常通过LeetCode所有测试用例。

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