问题描述：

---

题解：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9, p = 1e9 + 7;

int prefix[N],dp[N];

int main()
{
  int n, k;cin >> n >> k;
  dp[0] = prefix[0] = 1;
  for(int i = 1; i <= n; i++)
  {
  	if(i - k - 1 < 1)dp[i] = 1;
  	else dp[i] = prefix[i - k - 1];  // prefix[i - k - 1]: dp[1]~dp[i - k - 1]的和
  	prefix[i] = (prefix[i - 1] + dp[i]) % p;  // 更新prefix[i]（方案总数） 
  }
  
  cout << prefix[n] << '\n';  // 
  return 0;
}

---

知识点：动态规划