NC68 跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：(1≤n≤40)
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)

示例1

 输入：2
返回值：2

说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入：7
返回值：21

解题思路：

第三项等于前两项之和 f(n) = f(n-1) + f(n-2)
参考以上公式，如何压缩代码运行的时间和空间

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number int整型
# @return int整型
#
# 方法一： 递归, (缺点：number越大，空间和时间的复杂度越大)
class Solution:
def jumpFloor(self, number: int) -> int:
if number < 3:
return number
return self.jumpFloor(number-1) + self.jumpFloor(number-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]

# 方法三： 动态规划
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

# 输入
aclass = Solution()
print(aclass.jumpFloor(int(input())))

最后

以上就是复杂自行车为你收集整理的NC68 跳台阶NC68 跳台阶的全部内容，希望文章能够帮你解决NC68 跳台阶NC68 跳台阶所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。