题解 05| #跳台阶#
跳台阶
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # @param number int整型 # @return int整型 class Solution: def jumpFloor(self, number: int) -> int: if number <= 2: return number a,b=1,2 for i in range(3,number+1): a,b=b,a+b return b b=Solution() print(b.jumpFloor(7))
一、解题思路
- 理解问题:青蛙一次跳1或2级台阶,求跳n级台阶共有多少种跳法
- 分析问题:分析不同级数台阶的跳法数关系(n级台阶的跳法数等于n-1级和n-2级台阶跳法数之和),发现可以用动态规划来解决这个问题
- 设计算法:选用动态规划方法,创建一个列表来存储每个子问题(每个级数上的跳法数量),这样在计算n级台阶时,可以利用之前已计算的结果
- 编写代码:将分析和设计的算法用python编写为一个函数
- 测试优化:使用不同输入测试实现方法,并调整算法优化性能,降低时间复杂度或空间复杂度
二、举一反三
如果青蛙能跳1级、2级、3级,求跳n级台阶共有多少种跳法
def three_num(n):
if n<3:
return max(1,n)
a,b,c=1,1,2
for i in range(3,n+1):
a,b,c=b,c,a+b+c
return c
print(three_num(int(input())))
- 当 n = 0 时,跳法数= 1(青蛙不跳,直接站在 0 级台阶上)
- 当 n = 1 时,跳法数 = 1(直接跳 1 级台阶)
- 当 n = 2 时,跳法数 = 2(分两种情况:1 级+1 级 台阶 或 直接跳 2 级台阶)
- 当 n = 3 时,跳法数 = 4(分四种情况:1 级+1 级+1 级 或 3 级 台阶 或 1 级+2 级 台阶 或 2 级+1 级 台阶)
设 F(n) 表示跳上 n 级台阶的跳法数,则递推关系为:
F(n) = F(n-1) + F(n-2) + F(n-3)
算法学习分析与整理 文章被收录于专栏
个人学习算法的文档整理与思考,举一反三,相爱相杀。