【算法】动态规划 70： 爬楼梯

【70】爬楼梯

假设你正在爬楼梯。需要 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 阶

提示：

1 <= n <= 45

分析

我们记 dp[i] 为到达第 i 阶的方法数。因为每次只能爬 1 阶或 2 阶：

• 当你到达第 i 阶时，上一跳要么是从 i − 1 阶跨 1 阶，要么是从 i − 2 阶跨 2 阶。

• 因此状态转移方程为

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

• 边界条件：

  • dp[1] = 1 （只有一步跨 1）
  • dp[2] = 2 （1+1 或 2）

由于题目给出 1 ≤ n ≤ 45，我们可以用 O(n) 的时间和 O(1) 的额外空间完成计算。

---

方法一：滚动数组（最优空间）

只需要用两个变量维护前两项即可。

// C++ 实现
class Solution {
public:int climbStairs(int n) {if (n <= 2) return n;int prev2 = 1;    // dp[1]int prev1 = 2;    // dp[2]int cur = 0;for (int i = 3; i <= n; ++i) {cur = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]prev2 = prev1;prev1 = cur;}return cur;}
};

# Python 实现
class Solution:def climbStairs(self, n: int) -> int:if n <= 2:return nprev2, prev1 = 1, 2  # 分别对应 dp[1], dp[2]for _ in range(3, n+1):prev2, prev1 = prev1, prev1 + prev2return prev1

• 时间复杂度：O(n)
• 空间复杂度：O(1)

---

方法二：递归 + 备忘录（Memoization）

虽然递归写法更直观，但没有优化的话会指数级爆炸。我们可以加一个数组或哈希表缓存已经计算过的结果。

// C++ 实现：递归 + 备忘录
class Solution {vector<int> memo;
public:Solution(int n) : memo(n+1, -1) {}int climbStairs(int n) {memo[0] = 1;  // 为了递归基线，定义到 0 阶有 1 种“空走”方法memo[1] = 1;return helper(n);}int helper(int i) {if (memo[i] != -1) return memo[i];// 从 i-1 阶跨 1，或 i-2 阶跨 2memo[i] = helper(i-1) + helper(i-2);return memo[i];}
};

# Python 实现：递归 + 备忘录
class Solution:def __init__(self):self.memo = {}def climbStairs(self, n: int) -> int:return self._dfs(n)def _dfs(self, i: int) -> int:if i <= 2:return iif i not in self.memo:self.memo[i] = self._dfs(i-1) + self._dfs(i-2)return self.memo[i]

• 时间复杂度：O(n) （每个状态最多计算一次）
• 空间复杂度：O(n) （递归栈深度 + 备忘录）

---

举例验证

• 当 n=2 时：
  dp[1]=1, dp[2]=2 ⇒ 返回 2

• 当 n=3 时：
  dp[1]=1, dp[2]=2, dp[3]=dp[2]+dp[1]=3 ⇒ 返回 3

以上两种方法都能在常数级空间或线性空间内，快速算出答案。