算法提高 超级玛丽（动态规划）
问题描述
大家都知道"超级玛丽"是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,....am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。
现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。
输入格式
第一行为两个整数n,m
第二行为m个整数，表示陷阱的位置
输出格式
一个整数。表示玛丽跳到n的方案数
样例输入
4 1
2
样例输出
1
方法一
思路：
从题意中我们知道这是一个台阶题只不过添加了一个不可以跳到陷阱里面的条件。我们知道台阶题是个经典的dfs递归题。我们可以知道题目中走台阶的步数可以一1步，也可以是2步。那么我们就可以知道函数的走的方法就是 dfs(x+1) dfs(x+2) 。我们到小道的长度时就存一种可能，那陷阱的话意思就是当我们走到陷阱时就应该退回当前的走法，换下种可能，那我们可以用数组存储陷阱然后当函数中的步数走道次陷阱就退回。
程序：
n,m=map(int,input().split())
a=list(map(int,input().split())) #存储陷阱的位置
con=0
def dfs(x):
global con
if x>=n: #到小路距离和超过时
if x==n:
con+=1
return
if a.count(x)==1: #排除走到陷阱的可能
return
dfs(x+1)#走1步
dfs(x+2)#走2步
dfs(1)
print(con)
方法二
思路：
我们有可以用动态规划的思想，当我们知道之前的步数时就可以用当前的小路长度减去可以走的步数累加就可以得到当前的次数。dp[i]=dp[i-1]+dp[i-2] 因为我们可以知道i-1 的可能数和i-2的可能数，i-1就是我现在最后一步走的是1步，如果当前是陷阱的时候就可以可能的步数。
程序：
n,m=map(int,input().split())
a=list(map(int,input().split()))#存储陷阱的位置
dp=[1 for i in range(50)]
dp[0]=0
for i in range(1,n+1): #当前的步数
if a.count(i)==1:
dp[i]=0
else:
dp[i]=dp[i-1]+dp[i-2] #最后一步是1步的可能和2步的可能的累加值
print(dp[n])
禁止转载。仅用于自己学习。对程序错误不负责。
