爬楼梯递归超时问题

Question

老师，我按照你讲的，写的记忆化搜索方法在leetcode执行后显示超时，具体代码如下：

class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        Arrays.fill(memo,-1);
       if(n ==1){
           return 1;
       }
       if(n ==2){
           return 2;
       }
       if(memo[n]==-1){
            memo[n] = climbStairs(n-1)+climbStairs(n-2);
       }
       return memo[n];
    }
}

这样是不是说明这个方法用时太长，不适合以后在leetcode上的这道题以及其他相关题用，只是当练习用用？

Answer 1

liuyubobobo 2020-09-05 12:50:07

在你的这个写法中，每一次递归调用 climbStairs，都会开辟一个 n + 1 大小的 memo，然后都会给这个 n + 1 大小的 memo 上所有元素附上初值 -1。

在对比一下课程中我的思路是怎样的？

Java 参考代码：https://git.imooc.com/coding-82/coding-82/src/master/09-Dynamic-Programming/Course%20Code%20%28Java%29/02-Climbing-Stairs/src/Solution1.java

继续加油！：）

• 提问者 慕粉3869017 #1

  感谢老师指点，这个是我java基础知识不扎实以及思考不深入导致的。