题解 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. 理解问题:青蛙一次跳1或2级台阶,求跳n级台阶共有多少种跳法
  2. 分析问题:分析不同级数台阶的跳法数关系(n级台阶的跳法数等于n-1级和n-2级台阶跳法数之和),发现可以用动态规划来解决这个问题
  3. 设计算法:选用动态规划方法,创建一个列表来存储每个子问题(每个级数上的跳法数量),这样在计算n级台阶时,可以利用之前已计算的结果
  4. 编写代码:将分析和设计的算法用python编写为一个函数
  5. 测试优化:使用不同输入测试实现方法,并调整算法优化性能,降低时间复杂度或空间复杂度

二、举一反三

如果青蛙能跳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)
    
算法学习分析与整理 文章被收录于专栏

个人学习算法的文档整理与思考,举一反三,相爱相杀。

全部评论

相关推荐

ResourceUtilization:差不多但是估计不够准确,一面没考虑到增长人口,另一方面也没考虑到能上大学的人数比例,不过我猜肯定只多不少
点赞 评论 收藏
分享
哥_留个offer先:跟他说,你这个最好用c#,微软就用c#Java不适合这个项目
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务