## 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];}
}
}
};