爬楼梯问题是动态规划的最经典的入门模型。它的核心思想是：要到达当前位置，它可以从以前的那个位置跳（转移）过来。
对于求方案数的经典模型可以总结为：
- 定义状态：
dp[i]为到达第 \(i\) 级楼梯的方案数。 - 最小子问题：
d[0] = 1，这里需要注意是从第 \(0\) 阶到第 \(n\) 阶，还是第 \(1\) 阶到第 \(n\) 阶。 - 转移方程：\(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])