当前位置：首页 > news >正文

LeetCode 70. Climbing Stairs 题解

news 2026/5/28 1:13:57

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 阶

解题思路

方法一：动态规划

思路：

定义dp[i]为爬到第i阶的不同方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]，因为爬到第i阶的方法数等于爬到第i-1阶的方法数加上爬到第i-2阶的方法数
初始化：dp[1] = 1，dp[2] = 2
遍历计算dp[3]到dp[n]

复杂度分析：

时间复杂度：O(n)，其中 n 是台阶数。需要遍历计算dp[3]到dp[n]。
空间复杂度：O(n)，需要一个长度为 n+1 的数组来存储状态。

方法二：动态规划（空间优化）

思路：

观察到dp[i]只依赖于dp[i-1]和dp[i-2]，因此可以使用两个变量来存储前两个状态，而不需要使用数组
初始化：prev = 1（表示dp[1]），curr = 2（表示dp[2]）
遍历计算dp[3]到dp[n]，每次更新prev和curr的值

复杂度分析：

时间复杂度：O(n)，其中 n 是台阶数。需要遍历计算dp[3]到dp[n]。
空间复杂度：O(1)，只需要常数级的额外空间。

方法三：矩阵快速幂

思路：

递推关系dp[i] = dp[i-1] + dp[i-2]可以表示为矩阵形式：
```
[dp[i] ] = [1 1] * [dp[i-1]] [dp[i-1]] [1 0] [dp[i-2]]
```
因此，我们可以使用矩阵快速幂来加速计算，将时间复杂度降低到 O(log n)

复杂度分析：

时间复杂度：O(log n)，其中 n 是台阶数。矩阵快速幂的时间复杂度是 O(log n)。
空间复杂度：O(1)，只需要常数级的额外空间。

代码实现

方法一：动态规划

class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 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]

方法二：动态规划（空间优化）

class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 prev = 1 # dp[1] curr = 2 # dp[2] for i in range(3, n + 1): next_val = prev + curr prev = curr curr = next_val return curr

方法三：矩阵快速幂

class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 # 定义矩阵乘法 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(matrix, power): result = [[1, 0], [0, 1]] # 单位矩阵 while power > 0: if power % 2 == 1: result = multiply(result, matrix) matrix = multiply(matrix, matrix) power //= 2 return result # 初始矩阵 matrix = [[1, 1], [1, 0]] # 计算 matrix^(n-2) matrix_n = matrix_pow(matrix, n - 2) # 结果为 matrix^(n-2) * [2, 1]^T return matrix_n[0][0] * 2 + matrix_n[0][1] * 1