c560 - SF 愛運動
題目描述
題目要求計算從 0 階走到 N 階樓梯的方法數，每次可以走 1 階或 3 階，並且必須經過所有指定的休息站。答案需要模 1000000007。
解題思路
這題可以使用動態規劃來解決。a[i] 表示到達第 i 階樓梯的方法數。初始化 a[0] = 1。然後，從 0 到 N 迭代，計算到達下一階的方法數。如果 i+1 和 i+2 都不是休息站，則可以從 i 階走 3 階到達 i+3 階，因此 a[i+3] 加上 a[i]。此外，a[i+1] 加上 a[i]，表示從 i 階走 1 階到達 i+1 階。每次計算完 a[i] 後，取模 1000000007。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long int n,m,a[100050]={1},k;
bool b[100050];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<m;++i){
cin >> k;
b[k]=1;
}
for(int i=0;i<=n;++i){
a[i]%=1000000007;
a[i+1]+=a[i];
if(b[i+1]==0&&b[i+2]==0)
a[i+3]+=a[i];
}
cout << a[n];
}