問題：
假設(shè)你正在爬樓梯呜舒，需要n步你才能到達(dá)頂部。但每次你只能爬一步或者兩步笨奠，你能有多少種不同的方法爬到樓頂部袭蝗？
分析：
其實就是斐波那契數(shù)列的應(yīng)用唤殴，遞推公式為： f(i) = f(i-1) + f(i-2)
可以直觀的使用遞歸，但是時間復(fù)雜度與規(guī)模n成指數(shù)關(guān)系到腥，下面介紹動態(tài)規(guī)劃解法朵逝。
代碼：
int climbStairs(int n) {
// 開一個長度為 n+1 的數(shù)組記錄狀態(tài)，也稱‘打表’
if(n==0){
return 1;
}
else if(n==1){
return 1;
}
int dp[n+1] ;
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
事實上乡范，由于i 只和前兩項有關(guān),我們還可以省下O(n)的空間復(fù)雜度配名，但時間復(fù)雜度并未改變
int climbStairs(int n) {
// write your code here
if(n==0){
return 1;
}
else if(n==1){
return 1;
}
int m1=1,m2=1;
for(int i=2;i<=n;i++){
m2 = m1+m2;
m1 = m2-m1;
}
return m2;
}
