题目

每次可以爬 1 阶或 2 阶，问爬到第 n 阶一共有多少种不同方法。

题目分析

这题最重要的不是算出答案，而是建立动态规划最基本的思考方式：

  • 状态是什么
  • 转移从哪里来
  • 初始条件是什么

只要这三件事清楚，代码反而是结果。

方法一：直觉解法

如果从终点倒推，到达第 n 阶的最后一步只有两种可能：

  • 从 n-1 走 1 步上来
  • 从 n-2 走 2 步上来

所以答案天然等于前两个状态之和。

方法二：优化思路

设 dp[i] 表示“到达第 i 阶的方法数”，那么：

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

由于每一步只依赖前两个状态，所以连完整数组都不一定需要，可以直接用滚动变量优化。

Go 实现

 1func climbStairs(n int) int {
 2    if n <= 2 {
 3        return n
 4    }
 5
 6    prev2, prev1 := 1, 2
 7    for i := 3; i <= n; i++ {
 8        cur := prev1 + prev2
 9        prev2 = prev1
10        prev1 = cur
11    }
12    return prev1
13}

复杂度分析

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

易错点

  • 不要忘记 n=1 和 n=2 的初始条件
  • 很多线性 DP 都能从数组优化成滚动变量
  • 如果状态定义本身模糊，后面的转移式通常也会跟着模糊

我的复盘

爬楼梯这题看起来简单，但它几乎把动态规划最核心的入门思路都串起来了。以后遇到新的 DP 题，我会优先先写状态定义，而不是急着写递推式。

关联题

  • 使用最小花费爬楼梯
  • 打家劫舍
  • 斐波那契数列