爬楼梯问题（Leetcode 第70题）

爬楼梯问题（Leetcode 第70题）

问题描述

假设你正在爬楼梯。每次你可以爬 1 个或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

问题分析

这道题可以看作是一个经典的动态规划问题，或者是斐波那契数列的变种。

思路分析

当你站在第 n 阶台阶时，你可以通过以下两种方式到达：

1. 从第 n-1 阶台阶走 1 个台阶到达。
2. 从第 n-2 阶台阶走 2 个台阶到达。

因此，我们可以通过状态转移方程来定义这个问题：

dp[n] = dp[n-1] + dp[n-2]

这意味着，爬到第 n 阶的方法数等于爬到第 n-1 阶和第 n-2 阶的方法数之和。

初始条件：

• dp[1] = 1：只有一种方式（一步到达第一阶）。
• dp[2] = 2：有两种方式（1 阶 + 1 阶，或者 2 阶）。

基于以上思路，我们可以使用动态规划（DP）来解决这个问题。

代码实现

class Solution:def climbStairs(self, n: int) -> int:a, b = 1, 1  # 初始化a和b，代表爬到第1阶和第2阶的方式数for i in range(n - 1):  # 从第1阶到第n阶a, b = b, b + a  # 更新a和b，分别代表上一阶和当前阶的方案数return b  # 返回最终到达第n阶的方法数

解释

• 我们用两个变量 a 和 b 来表示爬到当前台阶的方案数。
• 初始时，a 和 b 都是 1，因为爬到第 1 阶和第 2 阶的方法数各为 1。
• 然后通过 for 循环逐步更新 a 和 b，其中 a 存储上一步的值（dp[i-1]），b 存储当前的值（dp[i]）。
• 每次更新时，b = b + a，这是因为到达第 i 阶的方法数是从第 i-1 阶和第 i-2 阶跳过来，所以下一阶的方案数等于前两阶方案数之和。

时间和空间复杂度

时间复杂度

• O(n)：我们只需要遍历一次循环，时间复杂度为 O(n)。

空间复杂度

• O(1)：我们只使用了常量空间来存储 a 和 b，空间复杂度为 O(1)。

总结

这道题的本质是一个斐波那契数列问题，可以通过动态规划来求解。利用滚动数组优化，我们用两个变量 a 和 b 代替了原本需要存储的整个数组，极大地节省了空间。在时间复杂度上，由于只需要遍历一次，我们的解法是高效的。