c547 - Bert 爬樓梯
題目描述
題目要求計算爬 n 階樓梯的不同走法，每次可以走 1 階或 2 階。由於答案可能很大，需要對 1000000007 取模。
解題思路
這道題可以使用動態規劃解決。定義 dp[i] 為爬到第 i 階樓梯的不同走法數量。
爬到第 i 階樓梯，可以從第 i-1 階走 1 階爬上來，也可以從第 i-2 階走 2 階爬上來。
因此，dp[i] = dp[i-1] + dp[i-2]。
初始條件為 dp[1] = 1 (只有一種走法，走 1 階) 和 dp[2] = 2 (兩種走法，走 1+1 階或 2 階)。
由於題目要求對 1000000007 取模，因此在計算 dp[i] 時需要進行模運算。
題目給定的 n 的範圍是 1 到 10000，因此可以預先計算出 dp[1] 到 dp[10000] 的值，然後根據輸入的 n 直接輸出 dp[n]。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long int dp[10005]={1,1},n;
int main(){
for(int i=2;i<=10001;++i){
dp[i]=dp[i-1]+dp[i-2];
dp[i]%=1000000007;
}
while(cin >> n)
cout << dp[n] << "\n";
}