Help! Why this recursive java solution has TLE problem?


  • 0
    public class Solution {
    public int climbStairs(int n) {
       if(n==1) return 1;
       if(n==2) return 2;
       return climbStairs(n-1)+climbStairs(n-2);
    }
    

    }


  • 0

    Maybe need a status array to save some repeated results. use more space for less time...


  • 0
    S

    It exceeds the time limit because this recursive formula for finding the nth fibonacci number results in an exponential runtime of order n, which is more or less as bad as it gets. You're right, if you use an array to store previous values as you compute them, you can get the runtime to be linear. Note that you only need an array of length two in order to do this.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.