d212 - 東東爬階梯
題目描述
題目要求計算爬 n 階階梯的不同走法，每次可以走 1 階或 2 階。
解題思路
這道題目可以利用費波那契數列的特性來解決。爬 n 階階梯的走法數量等於爬 n-1 階的走法數量加上爬 n-2 階的走法數量。這是因為如果第一步走 1 階，則剩下 n-1 階；如果第一步走 2 階，則剩下 n-2 階。因此，可以使用動態規劃或直接計算費波那契數列來得到答案。程式碼中使用了迭代的方式計算費波那契數列。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int main (){
long long int n=0,i=1,j=2,ans=0;
while(cin >> n){
if(n>=3){
while(n>=3){
ans=i+j;
i=j;
j=ans;
n--;
}
cout << ans << endl;
ans=0;
i=1;
j=2;
}
else{
cout << n << endl;
}
}
}