您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode中如何解决爬楼梯问题
## 问题描述
LeetCode上的第70题"爬楼梯"(Climbing Stairs)是一个经典的动态规划入门题目。题目描述如下：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 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 阶
## 问题分析
### 理解问题
首先我们需要明确题目的要求：给定一个n阶的楼梯，每次可以爬1阶或2阶，求到达楼顶的总方法数。
### 寻找规律
让我们从小规模的例子入手，观察规律：
- n=1：只有1种方法（1）
- n=2：2种方法（1+1，2）
- n=3：3种方法（1+1+1，1+2，2+1）
- n=4：5种方法（1+1+1+1，1+1+2，1+2+1，2+1+1，2+2）
可以看到，随着n的增加，方法数似乎遵循斐波那契数列的规律：f(n) = f(n-1) + f(n-2)
### 数学证明
为什么这个规律成立？因为要到达第n阶楼梯，只有两种可能：
1. 从第n-1阶跨1步上来
2. 从第n-2阶跨2步上来
因此，到达第n阶的方法数等于到达n-1阶和n-2阶方法数之和。
## 解决方案
### 1. 递归法（暴力解法）
最直观的解法是使用递归：
```python
def climbStairs(n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return climbStairs(n-1) + climbStairs(n-2)
时间复杂度：O(2^n)，因为每次调用会产生两个子调用
空间复杂度：O(n)，递归栈的深度
这种方法虽然简单，但效率极低，因为存在大量重复计算。
为了避免重复计算，我们可以使用记忆化技术：
def climbStairs(n: int) -> int:
memo = {}
def helper(n):
if n in memo:
return memo[n]
if n == 1:
return 1
if n == 2:
return 2
memo[n] = helper(n-1) + helper(n-2)
return memo[n]
return helper(n)
时间复杂度：O(n)，每个子问题只计算一次
空间复杂度：O(n)，用于存储记忆化结果和递归栈
我们可以将递归转换为迭代，使用动态规划：
def climbStairs(n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
时间复杂度：O(n)
空间复杂度：O(n)，用于存储dp数组
观察到每次计算只需要前两个状态，可以进一步优化空间：
def climbStairs(n: int) -> int:
if n == 1:
return 1
first, second = 1, 2
for _ in range(3, n+1):
first, second = second, first + second
return second
时间复杂度：O(n)
空间复杂度：O(1)，只使用了常数空间
利用矩阵快速幂可以将时间复杂度降到O(log n)：
def climbStairs(n: int) -> int:
def multiply(a, b):
return [
[a[0][0]*b[0][0] + a[0][1]*b[1][0],
a[0][0]*b[0][1] + a[0][1]*b[1][1]
], [
a[1][0]*b[0][0] + a[1][1]*b[1][0],
a[1][0]*b[0][1] + a[1][1]*b[1][1]
]
def matrix_pow(mat, power):
result = [[1, 0], [0, 1]] # 单位矩阵
while power > 0:
if power % 2 == 1:
result = multiply(result, mat)
mat = multiply(mat, mat)
power //= 2
return result
if n == 1:
return 1
mat = [[1, 1], [1, 0]]
result = matrix_pow(mat, n-1)
return result[0][0]
时间复杂度：O(log n)
空间复杂度：O(1)
斐波那契数列有通项公式：
f(n) = (φ^n - ψ^n)/√5，其中φ=(1+√5)/2，ψ=(1-√5)/2
def climbStairs(n: int) -> int:
sqrt5 = 5 ** 0.5
phi = (1 + sqrt5) / 2
psi = (1 - sqrt5) / 2
return int((phi ** (n + 1) - psi ** (n + 1)) / sqrt5)
时间复杂度：O(1)（假设幂运算为常数时间）
空间复杂度：O(1)
注意：由于浮点数精度问题，这种方法在n较大时可能不准确。
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归 | O(2^n) | O(n) | 不推荐，仅用于理解 |
| 记忆化递归 | O(n) | O(n) | 递归思维，中等规模 |
| 动态规划 | O(n) | O(n) | 标准解法，易于理解 |
| 优化动态规划 | O(n) | O(1) | 推荐，空间最优 |
| 矩阵快速幂 | O(log n) | O(1) | 大规模n |
| 通项公式 | O(1) | O(1) | 理论价值高，实际可能不精确 |
爬楼梯问题是理解动态规划的绝佳入门题目。我们从最基础的递归解法出发，逐步优化到空间最优的动态规划解法，最后介绍了数学方法。在实际面试中，推荐使用优化后的动态规划解法，它既高效又易于理解和实现。
掌握这个问题的核心在于理解状态转移方程，并能够根据不同的约束条件调整解决方案。这种分析问题和逐步优化的思路，对于解决其他算法问题同样重要。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。