解题思路:
动态规划计数问题。
动态规划求解步骤:
第一步:确定状态。
①最后一步:也就是问题的最后一步,这里的最后一步是走到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分
4 人评分
这可能是一个假的冒泡法浏览:985 |
输出正反三角形 (C语言代码)格式错误!!!浏览:1140 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:531 |
1011题解浏览:760 |
1048题解(读入回车问题)浏览:554 |
震宇大神的杀毒软件 (C语言代码)浏览:1079 |
明明的随机数 (C语言代码)浏览:953 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:525 |
哥德巴赫曾猜测 (C语言代码)浏览:714 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:438 |