当前位置:   article > 正文

华为机考攻略(python)--入门题【5题】(第五题递归:NC68跳台阶)_华为od青蛙跳台阶

华为od青蛙跳台阶

系列文章目录


前言

一、递归:NC68跳台阶

描述: 一只青蛙一次可以跳上一级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少中跳法(先后次序不同算不同的结果)
数据范围: 1<=n<=40
要求: 时间复杂度:O(n),空间复杂度:O(1)
示例1
输入:2
返回值:2
说明:青蛙要跳上两级台阶有两种:一种是先跳一级,再跳一级;另一种是直接跳两级;
示例2:
输入:7
返回值:21

二、sound code

1.sound code 1

递归:(缺点:number越大,空间和时间复杂度越大)

代码如下(示例):

class Solution:
     def jumpFloor(self, number: int) -> int:
         if number < 3:
             return number
         return self.jumpFloor(number-1) + self.jumpFloor(number-2)
s = Solution()
print(s.jumpFloor(int(input())))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

2.sound code 2

记忆化搜索

代码如下(示例):

class Solution:
    def jumpFloor(self,number:int)->int:
        v = {}
        for item in range(1,number+1):
            if item < 3:
                v[item] = item
            else:
                v[item] =v[item-1] + v[item-2]
        return v[number]
s = Solution()
print(s.jumpFloor(int(input())))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

动态规划

代码如下(示例):

class Solution:
    def jumpFloor(self,number:int)->int:
        if number < 3:
            return number
        a,b = 1,2
        for item in range(3,number):
            a,b = b,a+b
        return a+b 
s = Solution()
print(s.jumpFloor(int(input())))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

总结

分享:
为了实现梦想,人们必须做到极致,否则就会导致梦想折翼。沿着梦想的高地攀登,是一件非常悲壮的事,绝对没有什么诗情画意,也没有什么潺潺流水,有时甚至是知其不可为而为之。
真正能把梦想付诸实现的人,在哪个时代都是凤毛麟角。梦想如果不付诸行动,而止于梦想,这样的梦想就是空想,甚至连幻想和想象都算不上。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/146535
推荐阅读
相关标签
  

闽ICP备14008679号