爬楼梯递归超时问题

首页课程实战体系课手记专栏慕课教程

爬楼梯递归超时问题

来源：9-2 第一个动态规划问题 Climbing Stairs

慕粉3869017

2020-09-05

老师，我按照你讲的，写的记忆化搜索方法在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上的这道题以及其他相关题用，只是当练习用用？

写回答

1回答

liuyubobobo

liuyubobobo

2020-09-05

已采纳

在你的这个写法中，每一次递归调用 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

继续加油！：）

0

1

慕粉3869017

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

2020-09-05

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7433 学习 · 1159 问题

相似问题

lc203 递归写法复杂度分析

回答 1

关于视频中归并排序的递归时间复杂度分析的一点疑问

回答 2

在写递归算法时，会不会出现递归栈深度极深导致栈内存溢出的情况？

回答 1

lc160 怎样用递归写法呢？

回答 2

递归回溯时机？

回答 1

打开慕课网App查看更多内容