# Climbing Stairs

## Question

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?

Example
Given an example n=3 , 1+1+1=2+1=1+2=3

return 3


## 題解

1. State: f[i] 爬到第i級的方法數
2. Function: f[i]=f[i-1]+f[i-2]
3. Initialization: f[0]=1,f[1]=1

### C++

class Solution {
public:
/**
* @param n: An integer
* @return: An integer
*/
int climbStairs(int n) {
if (n < 1) {
return 0;
}

vector<int> ret(n + 1, 1);

for (int i = 2; i != n + 1; ++i) {
ret[i] = ret[i - 1] + ret[i - 2];
}

return ret[n];
}
};

1. 異常處理
2. 初始化n+1個元素，初始值均爲1。之所以用n+1個元素是下標分析起來更方便
3. 狀態轉移方程
4. 返回ret[n]

### Python

class Solution:
def climbStairs(n):
if n < 1:
return 0

l = r = 1
for _ in xrange(n - 1):
l, r = r, r + l
return r


### C++

class Solution {
public:
/**
* @param n: An integer
* @return: An integer
*/
int climbStairs(int n) {
if (n < 1) {
return 0;
}

int ret0 = 1, ret1 = 1, ret2 = 1;

for (int i = 2; i != n + 1; ++i) {
ret0 = ret1 + ret2;
ret2 = ret1;
ret1 = ret0;
}

return ret0;
}
};