Time Limited Error. Is this correct given that no time limitation?


  • 0
    T

    class Solution {
    public:
    int climbStairs(int n) {
    if (n<0) return 0;
    else if (n<=2) return n;
    else{
    int j,q;
    j=climbStairs(n-1);
    q=climbStairs(n-2);
    return j+q;
    }
    }
    };


  • 1
    A

    I think there is about a 2 second time limit on all problems, though I am not sure if that is the correct duration. But you could do a couple of things to speed up your solution.

    The first thing, and probably the easiest since your solution is already written recursively, is to memoize the states. So if you call climbStairs(5) and then later callStairs(5) gets called again, there is no point in calculating that state multiple times. Instead, you could retrieve the value from a lookup table of some sort. If you know the maximum value for n, you could create an array and initialize all values with some value to indicate that you have not calculated that value yet, such as a large value representing infinity or a negative value. Then each time you call this method, you first check to see if you have already calculated that state or not. If you have, simply return the value from the lookup table, otherwise perform the calculation and then store that in the lookup table for use later.

    Another way of doing this is to calculate it in a bottom up manner. This will involve rewriting your code so that you calculate the results of problem states from the smallest problem size up to the problem state that you are looking for. This will likely involve an array of size n+1. You could then set the values of the first three elements to 0, 1, and 2 respectively. Then you would start populating the remaining values using the values that you already calculated. For example, for n = 3 you would populate element 3 with the value of array[3-2] + array[3-1]. And for the general case you would populate element i with the value array[i-2] + array[i-1].

    Either of these approaches should work, though in this case the second approach of calculating the values in a bottom-up manner should be faster since you have to visit all states less than n anyway. But both of these should run in linear time whereas the way it is now the worst case time is exponential.


Log in to reply
 

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