代码随想录算法训练营第四十一天|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