线性dp-安全序列
问题描述
小蓝是工厂里的安全工程师，他负责安放工厂里的危险品。
工厂是一条直线，直线上有 n 个空位，小蓝需要将若干个油桶放置在 n 个空位上，每 2 个油桶中间至少需要 k 个空位隔开，现在小蓝想知道有多少种放置油桶的方案，你可以编写一个程序帮助他吗？
由于这个结果很大，你的输出结果需要对 10^9+7 取模。
输入格式
第一行包含两个正整数 n，k，分别表示 n 个空位与 k 个隔开的空位。
输出格式
输出共 1 行，包含 1 个整数，表示放置的方案数对 10^9+7 取模。
样例输入
4 2
样例输出
6
说明
用 0 代表不放，1 代表放，6 种情况分别为：
0000，1000，0100，0010，0001，1001。
评测数据规模
对于所有评测数据，1≤n≤10^6，1≤k≤n。
题解
dp[i]表示到第i个位置，可行的总方案数
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
ll p = 1e9 + 7;
ll dp[N];
int n,k;
int main(){
ios::sync_with_stdio(0),
cin.tie(0), cout.tie(0);
cin >> n >> k;
dp[0] = 1;
for(int i = 1;i <= n;i ++){
if(i - k - 1 < 1)dp[i] = (dp[i - 1] + 1) % p;
else dp[i] = (dp[i - 1] + dp[i - k - 1]) % p;
}
cout << dp[n] << '\n';
return 0;
}