题解 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)
    
算法学习分析与整理 文章被收录于专栏

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

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务