- 题目描述
- 解法一
- 解题思路
- python代码
- 小明刚刚看完电影《第 39 级台阶》,离开电影院的时候,他数了数礼堂前的台阶数, 恰好是 39 级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也 就是说一共要走偶数步。那么,上完 39 级台阶,有多少种不同的上法呢? 请你利用计算机的优势,帮助小明寻找答案。
动态规划 1.定义数组dp1,dp1[i]表示第i+1个台阶有dp1[i]种走法(不管是否要走了偶数步),定义数组dp2,dp2[i]表示第i+1个台阶有dp2[i]种走法(走了偶数步)。 2.益知dp1[0]=1,dp1[1]=2;dp2[0]=0,dp2[1]=1。 3.可推的dp1[i] = dp1[i-1]+dp2[i-2],dp2[i] = dp1[i-1]-dp2[i-1]+dp1[i-2]-dp2[i-2] 要到第i个台阶,那么i-1个台阶时必走了奇数步,或者i-2个台阶时必走了奇数步 所以dp2[i] = dp1[i-1]-dp2[i-1]+dp1[i-2]-dp2[i-2]python代码
n = 39 def f(n): dp1 = [1,2] dp2 = [0,1] for i in range(2,n): dp1.append(dp1[i-1]+dp1[i-2]) dp2.append(dp1[i-1]-dp2[i-1]+dp1[i-2]-dp2[i-2]) return dp2[-1] print(f(n))
运行结果
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)