Trying to implement a recursion but TLE when testing 44. Any suggestions?


  • 0
    F

    So I was trying to implement a straight forward recursive method when I got the TLE message on test case 44. I tried to run it on Eclipse and got a negative number while other smaller test case runs well. Anyone can help me with this problem? Many thanks.

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

    }


  • 1
    V

    TLE because the recursive calls are almost exponential.

    For ex:

    CS(4) = CS(3) + CS(2)

             = CS(2) + CS(1) + CS(1) + CS(0)
    
             = CS(1)  + CS(0) + CS(1) + CS(1) + CS(0)
    

    Though you are computing one value you are again calling it. If n is very large this leads to lot of redundant calls causing TLE.

    You can try saving already computed values in an array and resue them.
    Also, you can compute the values from bottom up instead of top down. This saves lot of time and space.
    Something like...

    ....
    store[0] = 1;
    store[1] = 1;
    for (i = 2; i <=n; i++)
        store[i] = store[i - 1] + store[i - 2];
    return store[n];
    ...
    

Log in to reply
 

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