蓝桥杯-安全序列


import os
import sys

MOD = 1000000007

n, k = map(int, input().split())

# dp[i] 表示前i个位置的方案数
dp = [0] * (n + 1)
dp[0] = 1  # 空集

for i in range(1, n + 1):
    # 方案数 = 不选i的方案数 + 选i的方案数
    # 不选i：dp[i-1]
    # 选i：那么上一个选的位置必须在 ≤ i-k-1
    if i - k - 1 >= 0:
        dp[i] = (dp[i-1] + dp[i - k - 1]) % MOD
    else:
        # 选i时前面没有位置可放，所以只加1（只放i这一个）
        dp[i] = (dp[i-1] + 1) % MOD

print(dp[n] % MOD)