代码随想录算法训练营第四十一天|509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

csdn推荐

好的,对于爬楼梯问题,我们可以使用斐波那契数列来解决。假设我们有 n 阶楼梯,每次可以爬 1 阶或 2 阶,那么到达第 n 阶楼梯的方法数就是到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数。因此,我们可以使用递归方法来求解,代码如下:“`pythondef climbStairs(n):if n == 1:return 1elif n == 2:return 2else:return climbStairs(n-1) + climbStairs(n-2)“`但是,递归方法的时间复杂度为 O(2^n),效率非常低,当 n 很大时,计算时间会非常长。因此,我们可以使用斐波那契数列的方法来优化求解过程。具体来说,我们可以使用两个变量 a 和 b 来记录到达当前楼梯所需要的方法数,初始值分别为 1 和 2。然后,我们可以使用循环来迭代计算,每次将 a 和 b 更新为 b 和 a+b,直到计算到第 n 阶楼梯为止。最后,返回 b 即可,代码如下:“`pythondef climbStairs(n):if n == 1:return 1elif n == 2:return 2else:a, b = 1, 2for i in range(3, n+1):c = a + ba = bb = creturn b“`使用这种方法,时间复杂度为 O(n),效率大大提高。

文章来源:https://blog.csdn.net/lixuan19940620/article/details/139223032



微信扫描下方的二维码阅读本文

© 版权声明
THE END
喜欢就支持一下吧
点赞8 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容