首页力扣70. 爬楼梯 Python

力扣70. 爬楼梯 Python

时间: 2025-04-26 11:53:17 浏览: 42

### LeetCode 70 题爬楼梯问题的 Python 实现对于给定的 `n` 步台阶，计算到达顶部的不同方法数可以采用动态规划的方法来解决。当 `n<=1` 时返回 1，因为只有一种方式达到顶点[^4]。定义数组 `a` 来存储每一步的结果，其中 `a[0]=1`, `a[1]=2` 表示前两步可能的方式数量。通过迭代更新此列表中的值直到处理完所有的 `n` 步： ```python class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n <= 1: return 1 a = [0] * n a[0] = 1 a[1] = 2 for i in range(2, n): a[i] = a[i - 1] + a[i - 2] return a[-1] ``` 上述代码中初始化了一个长度为 `n` 的零向量 `a` 并设定了边界条件 `a[0]=1` 和 `a[1]=2` 。接着利用循环填充剩余位置上的数值，最终返回最后一项即为所求结果。为了优化空间复杂度可以从线性表简化到仅需两个变量保存最近两次的状态即可完成相同功能: ```python def climbStairs_optimized(n): if n == 1 or n == 2: return n prev, curr = 1, 2 for _ in range(3, n + 1): temp = curr curr += prev prev = temp return curr ``` 这种方法不仅减少了内存占用还提高了执行效率[^5]。

阅读全文