Climb stairs exceed time limits, Why?


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

  • 11
    M

    The problem here is that you are doing a lot of the work multiple times. For instance, there is no difference between the paths from a given number if you got there by stepping up 1 stair twice or 2 stairs once. The number of ways to get to the top from that stair remains the same, but you are calculating it twice from scratch. Extend that to 4 stairs above your starting point. You could get there using 1-1-1-1, 2-1-1, 1-2-1, 1-1-2, or 2-2. You now need to calculate f(n-4) 4 times.

    To speed this up, you can remember the result for a given number of steps, then just use that result the next time you need that number instead of recalculating the entire process. This "remembering" is called memoization, and is required for quite a few of the problems on this site in order to complete them before the time limit.


  • 0
    C
    This post is deleted!

  • 0
    M

    Just noticed, you need to calculate f(n-4) 5 times, not 4.


  • 0
    S

    Answers you've written must describe your code with more detail content, and with correct code format. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 3
    G

    If n is big enough, you will do a lot of repeated computation which cause TLE.
    You have noticed that

    climbStairs(n) = climbStairs(n-1) + climbStairs(n-2);
    

    so you can write code in a not recursive way like

    vector<int> count(n + 1);
    count[0] = 0;
    count[1] = 1;
    count[2] = 2;
    for (int i = 3; i <= n; ++i) {
        count[i] = count[i - 1] + count[i - 2];
    }
    return count[n];
    

    hope this can help you :D


  • 0
    S

    Yeah its a dynamic programming problem. You need to store the prev results as the sub problems are getting overlapped. Calculate the result once and use it when that problem solution is needed


  • 0
    Y
    class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        if n == 0:
            return 1
        elif n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n/2 + 1)*self.climbStairs(n- n/2 - 1) + self.climbStairs(n/2) * self.climbStairs(n - n/2 - 2)
    

    Complexity is much less by dividing than by Fibonaccing, I think.


Log in to reply
 

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