##
**Climbing Stairs**

You are climbing a stair case. It takes

*n*steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

### Analysis:

The easiest idea is a Fibonacci number. f(n) = f(n-1) + f(n-2). The nth stairs is from either n-1th the stair or the n-2th stair. However recursive is time-consuming. We know that recursion can be written in loop, the trick here is not construct a length of n array, only three element array is enough.

### Updated(201407) Code (DP, Python):

class Solution: # @param n, an integer # @return an integer def climbStairs(self, n): f1=1; f2=2; if n<3: return n for i in xrange(3,n+1): f2 = f1+f2; f1 = f2-f1; return f2

### Updated(201407) Code (DP,C++):

class Solution { public: int climbStairs(int n) { if (n<3){return n;} int f1=1; int f2=2; for (int i=3;i<=n;i++){ f2=f1+f2; f1=f2-f1; } return f2; } };

The source code (recursively):

Note that this code is used for illustration, might not pass the online test.

class Solution { public: int climbStairs(int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if (n<=2) {return n;} else { return climbStairs(n-1) + climbStairs(n-2); } } };

The source code (loop):

class Solution { public: int climbStairs(int n) { // Start typing your C/C++ solution below // DO NOT write int main() function int s[3]={0,1,2}; if (n<=2) {return s[n];} int j = 2; while (true){ j++; s[(j%3)] = s[((j+1)%3)] + s[((j+2)%3)]; if (j==n) {return s[j%3];} } } };

Recursive code say "Time Limit Exceeded : Last executed input: 44".

ReplyDeleteI don't know why it says that because the code looks perfect.

Yes, recursive code is time consuming and may not pass the test requirement.

DeleteHere I just want to show the recursive way for illurstrastion.

Please follow the DP and loop code for the online test.

I will add notes on the post. Thanks.