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