假設(shè)你正在爬樓梯跋破。需要 n 階你才能到達(dá)樓頂号涯。
每次你可以爬 1 或 2 個(gè)臺(tái)階绕娘。你有多少種不同的方法可以爬到樓頂呢亡驰？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂饿幅。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂凡辱。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
思路
計(jì)算當(dāng)樓梯數(shù)為1、2栗恩、3透乾、4、5時(shí)摄凡，對(duì)應(yīng)的爬法有：1续徽、2、3亲澡、5钦扭、8、13床绪、21種客情。
可以發(fā)現(xiàn)，隨著樓梯數(shù)n的增加癞己，爬法總數(shù)呈現(xiàn)斐波那契數(shù)列規(guī)律增加
class Solution {
public int climbStairs(int n) {
if(n==1||n==0){
return 1;
}
if(n==2){
return 2;
}
int f=1;
int s=2;
int r=0;
n=n-2;
while(n>0){
r=f+s;
f=s;
s=r;
n--;
}
return r;
}
}
