E001 爬楼梯方案数 有损坏的楼梯

爬楼梯问题是动态规划的最经典的入门模型。它的核心思想是：要到达当前位置，它可以从以前的那个位置跳（转移）过来。

对于求方案数的经典模型可以总结为：

1. 定义状态： dp[i] 为到达第 \(i\) 级楼梯的方案数。
2. 最小子问题：d[0] = 1 ，这里需要注意是从第 \(0\) 阶到第 \(n\) 阶，还是第 \(1\) 阶到第 \(n\) 阶。
3. 转移方程：\(dp_i=\sum dp[i-step]\) ，要注意在 i - step 的时候防止越界。

---

基础模型：每次跳 \(1\) 或 \(L\) 步

这是最通用的形式，当 \(L=2\) 时就是最经典的斐波那契数列

Stair Jump - AtCoder

参考代码

def main():n, L = MII()MOD = 10 ** 9 + 7dp = [0] * (n + 1)dp[0] = 1for i in range(1, n + 1):dp[i] += dp[i - 1]if i - L >= 0:dp[i] += dp[i - L]dp[i] %= MODprint(dp[n])

---

变体：避开损坏的台阶

如果楼梯有损坏，那么损坏的楼梯就不更新了，直接 continue 。使用一个集合存损坏的楼梯。

Typical Stairs - AtCoder

参考代码

def main():n, m = MII()a = set(II() for _ in range(m))dp = [0] * (n + 1)# 只初始化第0阶，第一阶有可能损坏dp[0] = 1for i in range(1, n + 1):if i not in a:dp[i] = (dp[i - 1] + dp[i - 2]) % MOD  # 这里访问dp[-1]没有影响print(dp[n])