斐波那契数列的公式为
```
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
```
最直观的方式是使用递归，但是递归需要一定的栈空间，而且有重复计算，例如：f(8) = f(7) + f(6),f(7) = f(6) + f(5) 这样，会多次计算，可以使用循环的方式，每次计算之后累加，如从f(2)开始，一直计算到f(n)，期间一直保存这f(cur-1),f(cur-2)
递归程序
```
public int get(int i) {
if(i<0)return -1;
if(i == 0||i == 1)return i;
return get(i-1) + get(i-2);
}
```
循环程序
```
public int get(int i) {
if(i < 0) return -1;
if(i == 0||i == 1)return i;
int N$2 = 0, N$1 = 1,idx = 2,ret=0;
while(idx <= i) { // 0 1 1 2 3 5 8
ret = N$2 + N$1;
N$2 = N$1;
N$1 = ret;
idx++;
}
return ret;
}
```
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法，返回3
**规则**
输入： int n 楼梯的长度
输出：int 多少种方法
case：
```
n 小于0
n等于0
n等于1
n等于2
```
**思路**
假设第n个台阶有f(n)种方法，f(n-1)种再加上一步1个台阶就到达n了，此时有f(n-1)种，f(n-2)楼梯的时候再加上一步2个台阶就到达n了，此时有f(n-2)种，因此：f(n) = f(n-1)+f(n-2)，f(0) = 0 ，f(1) = 1 f(2) = 2
**代码**
```
public int climbStairs(int i) {
if (i <= 0) {
return 0;
}
if (i == 1) {
return i;
}
int N$2 = 1, N$1 = 1, idx = 2, ret = 0;
while (idx <= i) { // 0 1 1 2 3 5 8
ret = N$2 + N$1;
N$2 = N$1;
N$1 = ret;
idx++;
}
return ret;
}
```
