蓝桥杯算法提高VIP-超级玛丽-题解（Python代码）动态规划计数问题详解

解题思路:
    动态规划计数问题。

    动态规划求解步骤：

        第一步：确定状态。

                        ①最后一步：也就是问题的最后一步，这里的最后一步是走到n

                        ②子问题：本题中可以走1~2步，所以最后一步前状态有两个n-1，n-2

        第二步：状态转移方程。

                        状态出来了转移方程就出来了是f[n] = f[n]+f[n-1]  ,f[n] = f[n]+f[n-2]

        第三步：初始条件，边界情况。

                        初始条件：往往都是通过转移方程算不出来的，而可以看的出来的。这里是位置1时移动的方法只有1种。

                        边界情况：列表不要越界，还有题中的陷阱。

        第四步：计算顺序。

                        根据转移方程f[n] = f[n]+f[n-1]，算f[n]时f[n-1]必须算过了所以可以知道是从小到大的顺序。

    理清楚之后就可以写代码了。

参考代码:

n,m = map(int,input().split())
xl = list(map(int,input().split()))
dp = [0 for _ in range(n+1)]
dp[1] = 1        #初始状态
for i in range(n+1):    #计算顺序
    for j in [1,2]:
        if i-j>=1 and xl.count(i) == 0:    #边界情况
            dp[i] = dp[i-j] + dp[i]    #转移方程
print(dp[n])