爬楼梯问题是算法面试中的高频题目，描述很简单：假设你正在爬楼梯，每次可以爬1级或2级台阶，那么爬到第n级台阶一共有多少种不同的方法？这个问题之所以经典，是因为它几乎涵盖了动态规划的所有核心思想——状态定义、状态转移方程、边界条件、空间优化。把这道题吃透，再去看背包问题、最长公共子序列等复杂DP题目，思路会清晰很多。
从暴力递归看问题的数学本质
面对爬楼梯问题，最容易想到的思路是手动枚举。比如n等于3时，可以列出三种方案：1＋1＋1、1＋2、2＋1。但是当n增大到10、20甚至50时，枚举就完全不现实了。此时需要换一个角度：把问题看成是多个子问题的组合。
假设我们要爬到第n级台阶，最后一步只有两种可能：从第n－1级跨1级上来，或者从第n－2级跨2级上来。因此，爬到第n级的方法总数，恰好等于爬到第n－1级的方法数加上爬到第n－2级的方法数。写成数学表达式就是f(n)=f(n-1)+f(n-2)，这就是著名的状态转移方程。边界条件也很明确：f(1)=1，f(2)=2。
这个递推关系让人联想到斐波那契数列，只是初始值不同。根据这个方程，直接用递归函数就能翻译成代码。下面是一段用Go语言实现的暴力递归版本：
package main
import "fmt"
// climbStairsBrute 暴力递归求解爬楼梯
func climbStairsBrute(n int) int {
if n <= 2 {
return n
}
return climbStairsBrute(n-1) + climbStairsBrute(n-2)
}
func main() {
fmt.Println(climbStairsBrute(10)) // 输出 89
}
这段代码的逻辑完全符合递推关系，但性能非常糟糕。以计算f(5)为例，递归会先计算f(4)和f(3)，而f(4)又要计算f(3)和f(2)，其中f(3)被重复计算了两次。随着n增大，这种重复计算呈指数级增长。f(40)就已经需要数亿次函数调用，运行时间以秒计，n一旦过百，程序基本跑不完。
备忘录递归：自顶向下的动态规划
暴力递归慢就慢在同一个子问题被反复求解。解决思路很直接：把每次计算出的结果存起来，下次遇到相同参数时直接返回缓存值，不再递归。这种缓存机制在动态规划里叫作备忘录，对应的解法称为带备忘录的递归，或者自顶向下的动态规划。
所谓自顶向下，指的是思考顺序还是从f(n)开始，逐层向下分解成f(n-1)和f(n-2)，直到碰到已知的边界条件。只不过在向下分解的过程中，会用数组把已经算出的中间结果记录下来。下面给出带备忘录的Go实现：
package main
import "fmt"
// climbStairsWithMemo 带备忘录的递归解法
func climbStairsWithMemo(n int) int {
memo := make([]int, n+1)
return helper(n, memo)
}
func helper(n int, memo []int) int {
if n <= 2 {
return n
}
// 如果备忘录里已经有结果，直接返回
if memo[n] != 0 {
return memo[n]
}
memo[n] = helper(n-1, memo) + helper(n-2, memo)
return memo[n]
}
func main() {
fmt.Println(climbStairsWithMemo(20)) // 输出 10946
}
这段代码的时间复杂度从指数级降到了O(n)。因为每个n值最多只会被真正计算一次，其余访问都是O(1)的查表操作。空间复杂度为O(n)，主要消耗在备忘录数组和递归调用栈上。
使用备忘录递归时有一个容易忽略的细节：初始值的选择。上述代码用0作为“未计算”的标记，这依赖f(1)和f(2)都大于0这个事实。如果题目改成初始状态可能是0的场景，就得换用其他标记方式，比如把备忘录初始化为-1，或者单独用一个布尔数组记录计算状态。另外，递归深度受限于系统栈，当n超过一万级别时，即使时间上能承受，递归调用也可能导致栈溢出，这是自顶向下方案的一个天然短板。
迭代法：自底向上的动态规划
既然f(n)只依赖f(n-1)和f(n-2)，那完全可以从已知的边界条件出发，从小到大依次推导。这就是自底向上的动态规划，一般用循环加数组来实现，也被称为递推解法。整个过程不需要递归，也就不存在栈溢出的风险。
先定义一个dp数组，dp[i]表示爬到第i级台阶的方法数。初始化dp[1]为1、dp[2]为2，然后从i等于3开始循环，每次用dp[i-1]+dp[i-2]更新dp[i]。循环结束后，dp[n]就是要求的答案。下面是对应的Go代码：
package main
import "fmt"
// climbStairsDP 自底向上的动态规划
func climbStairsDP(n int) int {
if n <= 2 {
return n
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
func main() {
fmt.Println(climbStairsDP(10)) // 输出 89
}
这段代码的时间复杂度同样是O(n)，空间复杂度为O(n)。但仔细看状态转移方程会发现，计算dp[i]时只用到了dp[i-1]和dp[i-2]，更早的状态用完之后就再也不需要了。既然如此，完全可以用两个变量滚动前进，把空间复杂度压缩到O(1)。这种优化思路在实际工程中非常常见，当n很大时，O(n)的数组可能占用上兆内存，而滚动变量只占用两个整数空间。
package main
import "fmt"
// climbStairsOpt 空间优化版迭代解法
func climbStairsOpt(n int) int {
if n <= 2 {
return n
}
prev, curr := 1, 2 // prev 表示 f(i-2)，curr 表示 f(i-1)
for i := 3; i <= n; i++ {
prev, curr = curr, prev+curr
}
return curr
}
func main() {
fmt.Println(climbStairsOpt(50)) // 输出 20365011074
}
要注意n过大时f(n)会超出int类型的表示范围。上面例子中n等于50时结果是20365011074，已经超过32位整数的上限。在实际开发中，要根据题目要求和语言特性选择合适的数据类型，比如Go里可以用uint64，Python里直接用int即可，而Java则建议改用long甚至BigInteger。
三种方案对比与实战选型建议
把暴力递归、备忘录递归、迭代法放在一起看，能更清楚地理解各自的定位。暴力递归的优点是代码最贴近递推公式、最容易理解，缺点是存在大量重复计算，只能在n很小的时候使用。备忘录递归在暴力递归的基础上增加了缓存，思路仍然是自顶向下，适合那些递推关系直观、但正向推导比较绕的问题。
迭代法是最推荐掌握的方案，尤其是空间优化版本。它不仅没有递归栈溢出的风险，而且时间和空间表现都是最优的。在实际面试中，多数面试官期待的第一个优化版本就是O(n)时间、O(1)空间的迭代写法。当然，如果面试官先问解题思路，从暴力递归说起再逐步优化，反而是展示你思维过程的加分项。
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力递归 | O(2^n) | O(n)（递归栈） | 仅用于理解递推关系 |
| 备忘录递归 | O(n) | O(n) | 递推关系清晰但要求保留原递归逻辑 |
| 迭代加数组 | O(n) | O(n) | 入门教学，便于追踪每一步状态 |
| 迭代滚动变量 | O(n) | O(1) | 面试与工程实践的首选 |
最后总结一下动态规划的通用套路。拿到一个递推型问题，先明确状态定义，也就是dp[i]代表什么；然后推导状态转移方程，寻找当前状态和之前状态的关系；接着写清楚边界条件；最后考虑能否用滚动变量压缩空间。爬楼梯问题完全覆盖了这四个步骤，把这套流程烂熟于心，再遇到类似的跳台阶、矩形覆盖、斐波那契变种题，就能迅速套用。
如果觉得递归和迭代的取舍不好把握，这里给一个简单判断原则：当递推关系是单向的、只依赖前若干项时，优先选择迭代；当问题可以分解为多个相互独立又存在重叠的子问题时，比如树形结构的遍历和分治类题目，备忘录递归往往更好写、更好调试。理解了这两种范式的适用边界，才算真正掌握了动态规划的核心思想。