妙先生


私信TA

用户名:uq_57083779177

访问量:1954

签 名:

妙啊!

等  级
排  名 461
经  验 2887
参赛次数 0
文章发表 73
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

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

    动态规划求解步骤:

        第一步:确定状态。

                        ①最后一步:也就是问题的最后一步,这里的最后一步是走到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])


 

0.0分

1 人评分

  评论区