python算法爬楼梯
python算法爬楼梯
·
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。请问有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数,其范围为:1 ≤ n ≤ 100。
方法一:直接递归法
def func(n):
if n == 1 or n == 2:
return n
return func(n - 1) + func(n - 2)
print(func(6))
当n比较大时,这种方法效率很低。
方法二:递归、保存中间值法
把计算过的值存入字典,防止重复计算
如计算f(6),需要求f(5)和f(4),计算f(5)需要求f(4)和f(3),那么f(4)就被重复计算了
adict = {}
def func(n):
if n == 1 or n == 2:
return n
if adict.get(n,None) != None:
return adict.get(n,None)
else:
result = func(n - 1) + func(n - 2)
adict[n] = result
return result
print(func(6))
这种方法效率会高很多,其实也可以通过循环来实现
方法三:循环法,自底向上累加
def func(n):
a, b = 1, 1
while n > 1:
a, b = b, a + b
n -= 1
return b
print(func(6))
这种方法的效率也很高
参考
视频:https://www.bilibili.com/video/BV1eg411w7gn?p=5&spm_id_from=pageDriver&vd_source=0467ab39cc5ec5940fee22a0e7797575
文章:https://www.jianshu.com/p/301f7bb7b574
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献13条内容
所有评论(0)