思路:
解决爬楼梯问题,其中 n
表示楼梯的阶数。问题的描述是:每次可以爬1个或2个台阶,问有多少种不同的方法可以爬到楼梯的顶部。
算法思路如下:
- 初始时,设定变量
a
和b
分别表示爬到当前阶数所需的步数,初始化为1,因为爬到第1阶和第2阶只需1步。 - 使用循环从第3阶开始遍历到第
n
阶,每次更新a
和b
的值,更新规则是a
变为b
,b
变为a + b
,这是因为到达当前阶数的方法数等于到达前一阶和前两阶的方法数之和。 - 循环结束后,返回
b
,即到达第n
阶的方法数。
这个算法的时间复杂度是 O(n),因为只需要遍历一次楼梯的阶数。
python">class Solution:def climbStairs(self, n: int) -> int:# 初始时,a和b分别表示爬到第1阶和第2阶所需的步数,初始化为1,因为只有1阶和2阶时,分别需要1步a, b = 1, 1# 从第3阶开始遍历到第n阶for _ in range(n - 1):# 更新a和b的值,更新规则是a变为b,b变为a+b# 这是因为到达当前阶数的方法数等于到达前一阶和前两阶的方法数之和a, b = b, a + b# 循环结束后,b表示到达第n阶的方法数return b