华为 OD 训练营 · 题解精讲
LC70. 爬楼梯
配套讲解：视频讲解 ↗
LC70. 爬楼梯 视频地址：https://uha.xet.tech/s/4uamcb
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 提示： 1 <= n <= 45
题目解析
解题思路
本题是经典的斐波那契数列问题。到达第 n 阶的方法数等于到达第 n-1 阶的方法数（再爬 1 阶）加上到达第 n-2 阶的方法数（再爬 2 阶），即递推公式 f(n) = f(n-1) + f(n-2)，边界条件为 f(1)=1、f(2)=2。
参考代码给出了三种实现方式，但实际做法完全一致：动态规划（自底向上）。第三种代码是最终版本，使用数组 memo 记录子问题的解，从 3 到 n 依次计算，避免了递归重复计算。
关键步骤
1. 处理边界：n=1 返回 1，n=2 返回 2。 2. 初始化数组：memo = [0] * (n+1)，并设置 memo[1]=1、memo[2]=2。 3. 递推计算：从 i=3 到 n，执行 memo[i] = memo[i-1] + memo[i-2]。 4. 返回结果：return memo[n]。
递推过程示意（以 n=4 为例）：
memo[1]=1, memo[2]=2
i=3: memo[3] = memo[2] + memo[1] = 2+1=3
i=4: memo[4] = memo[3] + memo[2] = 3+2=5复杂度分析
- 时间复杂度：
O(n)，只需一次线性遍历。 - 空间复杂度：
O(n)，使用长度为n+1的数组存储中间结果。
参考代码
class Solution:
def climbStairs(self, n):
return self.calcWays(n)
def calcWays(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.calcWays(n - 1) + self.calcWays(n - 2)
代码
class Solution:
def climbStairs(self, n):
self.memo = [-1] * (n + 1)
return self.calcWays(n)
def calcWays(self, n):
if n == 1:
return 1
if n == 2:
return 2
if self.memo[n] == -1:
self.memo[n] = self.calcWays(n - 1) + self.calcWays(n - 2)
return self.memo[n]
代码
class Solution:
def climbStairs(self, n):
if n == 1:
return 1
if n == 2:
return 2
memo = [0] * (n + 1)
memo[1] = 1
memo[2] = 2
for i in range(3, n + 1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]