斐波那契數列的公式為
```
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;
}
```
