【题目来源】
蓝桥云课：1.破损的楼梯 - 蓝桥云课 (lanqiao.cn)
【题目描述】
小蓝来到了一座高耸的楼梯前，楼梯共有 \(N\) 级台阶，从第 \(0\) 级台阶出发。小蓝每次可以迈上 \(1\) 级或 \(2\) 级台阶。但是，楼梯上的第 \(a_1\) 级、第 \(a_2\) 级、第 \(a_3\) 级，以此类推，共 \(M\) 级台阶的台阶面已经坏了，不能踩上去。
现在，小蓝想要到达楼梯的顶端，也就是第N级台阶，但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数?
由于方案数很大，请输出其对 \(10^9+7\) 取模的结果。
【输入】
第一行包含两个正整数 \(N(1≤N≤10^5)\) 和 \(M(0≤Ｍ≤N)\)，表示楼梯的总级数和坏了的台阶数。
接下来一行，包含 \(M\) 个正整数 \(a_1,a_2,...,a_M(1≤a_1<a_2<a_3<a_M≤N)\)，表示坏掉的台阶的编号。
【输出】
输出一个整数，表示小蓝到达楼梯顶端的方案数，对 \(10^9+7\) 取模。
【输入样例】
6 1
3
【输出样例】
4
【算法标签】
《蓝桥云课 3367 破损的楼梯》 #动态规划#
【代码详解】
n, m = map(int, input().split()) # 读取台阶总数n和坏台阶数量m
a = list(map(int, input().split())) # 读取坏台阶的位置列表# 初始化动态规划数组和标记数组
dp = [0] * (n + 1) # dp[i]表示到达第i阶台阶的方法数
vis = [0] * (n + 1) # vis[i]标记第i阶是否是坏台阶# 标记所有坏台阶
for x in a:vis[x] = 1# 基础情况处理
dp[0] = 1 # 在地面（第0阶）有1种方法（不动）
dp[1] = 1 - vis[1] # 第1阶如果不是坏台阶则有1种方法# 动态规划递推
for i in range(2, n + 1):if vis[i] == 1: # 如果是坏台阶，跳过continue# 状态转移方程：可以从i-1或i-2阶跳上来dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007 # 取模防止溢出print(dp[n]) # 输出到达第n阶的方法数
【运行结果】
6 1
3
4