#1.破损的楼梯

"""

这段代码是用来计算小蓝到达楼梯顶端的方案数，其中楼梯共有V级台阶，从第0级台阶出发。

小蓝每次可以迈上1级或2级台阶，但是楼梯上的一些台阶已经坏了，不能踩上去。现在要求计算小蓝有多少种不踩坏的台阶到达顶端的方案数，并对结果取模。

首先，定义了一个长度为N的数组vis和f，并将它们初始化为0。

然后，读取输入数据，包括楼的总级数n和坏掉的台阶数m，以及坏掉的台阶编号X。

接下来，遍历坏掉的台阶编号X，将对应的vis数组位置设为1，表示该台阶已经坏了。

接着，设置初始条件，即到达第0级台阶只有一种方法，即不迈步，所以f[0]赋值为1；

到达第1级台阶有两种方法，要么不迈步，要么迈一步，所以f[1]赋值为1减去vis[1]的值。

然后，使用一个循环从第2级台阶开始遍历到第n级台阶。如果当前台阶已经坏了（vis[i]为真），则跳过当前迭代。

否则，计算到达当前台阶的方法数，即到达前一级台阶的方法数加上到达前两级台阶的方法数，并对结果取模。最后，输出到达第n级台阶的方法数。

"""

N = 100010

MOD = 1000000007

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

vis = [0] * N

f = [0] * N

X = list(map(int, input().split()))

for x in X:

vis[x] = 1

f[0] = 1

f[1] = 1 - vis[1]

for i in range(2, n + 1):

if vis[i]:

continue

f[i] = (f[i - 1] + f[i - 2]) % MOD

print(f[n])

#2.安全序列

'''

这段代码是动态规划中的一种常见模式，用于解决一些计数问题。这里的 `dp[i]` 表示到达第 `i` 步的方案数。

1. `if i - k - 1 >= 0:` 这一行判断当前位置 `i` 是否大于等于 `k+1`。

如果是，那么说明存在至少 `k+1` 个位置可以放置油桶，也就是说，我们可以从前 `i-k-1` 步的任何位置移动到第 `i` 步。

2. `dp[i] = (dp[i - 1] + dp[i - k - 1]) % MOD`

如果满足上述条件，那么我们可以从前 `i-1` 步和前 `i-k-1` 步的方案数之和得到第 `i` 步的方案数。

这是因为我们可以选择从前 `i-1` 步直接移动到第 `i` 步，也可以从前 `i-k-1` 步移动到第 `i` 步。然后对结果取模，防止结果过大。

3. `else:` 如果 `i` 小于 `k+1`，那么说明没有足够的位置可以放置油桶，我们只能从前 `i-1` 步移动到第 `i` 步。

4. `dp[i] = (dp[i - 1] + 1) % MOD` 在这种情况下，我们的方案数就是前 `i-1` 步的方案数加一。然后对结果取模，防止结果过大。

'''

MOD = 1000000007

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

dp = [0] * (n + 1)

# 初始状态：不放置也为一种方案

dp[0] = 1

for i in range(1, n + 1):

if i - k - 1 >= 0:

# i>=k-1：dp[i -1]：不放置 dp[i -k-1]:放置

dp[i] = (dp[i - 1] + dp[i - k - 1]) % MOD

else:

# i

dp[i] = (dp[i - 1] + 1) % MOD

print(dp[n])

好文链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。