# Climb stairs exceed time limits, Why?

• ``````    class Solution {
public:
int climbStairs(int n) {

if (n <= 2)
{
return n;
}
else
{
return climbStairs(n-1) + climbStairs(n-2);
}
}
};``````

• 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.

• This post is deleted!

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

• 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];
``````

• 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

• ``````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.

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