从递归到滚动数组：爬楼梯问题的四种解法演进与实战剖析-平芜编程栈

1. 从生活场景理解爬楼梯问题

第一次遇到这个算法题是在面试现场，当时面试官笑眯眯地问我："假设你每天上班要爬10层楼梯，每次可以跨1阶或者2阶，有多少种不同的上楼方式？"我愣了一下——这不就是斐波那契数列吗？后来在实际开发中才发现，这个看似简单的题目蕴含着算法优化的经典思维路径。

让我们用更生活化的例子理解：假设你要去朋友家做客，他家住4楼。你可以选择：

一步步慢慢走（1+1+1+1）
偶尔跨两步（1+2+1）
开始就跨两大步（2+2）总共有5种不同的上楼方案。这个数字规律很有意思：4阶对应5种方法，5阶对应8种...这不就是斐波那契数列吗？发现这个规律后，我们就能用算法来精确计算任意阶数的方案数了。

2. 暴力递归解法：最直观的思考起点

2.1 递归的实现与局限

初学者的第一反应往往是用递归解决，代码确实简洁得惊人：

def climb_stairs(n): if n <= 2: return n return climb_stairs(n-1) + climb_stairs(n-2)

这个解法完美体现了分治思想：要到达第n阶，要么从n-1阶跨1步，要么从n-2阶跨2步。我曾在白板上画过它的调用树，当n=5时：

climb_stairs(5) ├── climb_stairs(4) │ ├── climb_stairs(3) │ │ ├── climb_stairs(2) │ │ └── climb_stairs(1) │ └── climb_stairs(2) └── climb_stairs(3) ├── climb_stairs(2) └── climb_stairs(1)

2.2 性能瓶颈分析

但当我尝试计算climb_stairs(40)时，程序明显卡顿了。通过打印调用次数发现：计算n=40时递归函数被调用了超过2亿次！这是因为存在大量重复计算，比如climb_stairs(3)就被计算了3次。

时间复杂度方面，递归树每个节点会分裂出两个子节点，形成指数级增长。具体来说：

时间复杂度：O(2^n)（满二叉树节点数）
空间复杂度：O(n)（调用栈深度）

3. 记忆化递归：用空间换时间的优化

3.1 引入缓存机制

面对重复计算问题，我首先想到用字典缓存计算结果：

memo = {} def climb_stairs(n): if n in memo: return memo[n] if n <= 2: return n memo[n] = climb_stairs(n-1) + climb_stairs(n-2) return memo[n]

这个优化效果立竿见影——计算n=40从几分钟降到毫秒级。因为每个子问题只需要计算一次，后续直接读取缓存。

3.2 性能对比实测

在我的笔记本上测试（Python 3.8）：

原始递归：n=30需要约3秒
记忆化递归：n=100仅需0.1毫秒

不过这种写法有个小缺点：全局变量memo可能引发副作用。更安全的实现是用装饰器：

from functools import lru_cache @lru_cache(maxsize=None) def climb_stairs(n): if n <= 2: return n return climb_stairs(n-1) + climb_stairs(n-2)

4. 动态规划：自底向上的迭代思维

4.1 标准DP实现

递归虽然直观，但容易栈溢出。动态规划改用迭代方式：

def climb_stairs(n): if n <= 2: return n dp = [0]*(n+1) dp[1], dp[2] = 1, 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

这个解法有几点优势：

没有递归开销
计算顺序明确可控
更容易添加边界条件处理

4.2 DP状态转移分析

关键在于理解状态转移方程：

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

这表示到达第i阶的方法数等于：

从i-1阶跨1步的方案数
从i-2阶跨2步的方案数

我在教学时常用这个比喻：把楼梯想象成游戏关卡，每个关卡的通关方法取决于前两个关卡的选择。

5. 滚动数组：极致的空间优化

5.1 空间复杂度优化

观察DP解法发现：计算dp[i]只需要前两个状态。于是可以压缩空间：

def climb_stairs(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n+1): a, b = b, a+b return b

这个版本的空间复杂度从O(n)降到O(1)，是面试官最期待的写法。变量交替前进的过程就像三个齿轮互相咬合滚动。

5.2 多种语言实现对比

在C++中需要注意整数溢出问题：

int climbStairs(int n) { if(n <= 2) return n; int a = 1, b = 2; for(int i=3; i<=n; ++i){ int c = a + b; a = b; b = c; } return b; }

而在JavaScript中可以利用解构赋值：

function climbStairs(n) { let [a, b] = [1, 2]; for(let i=3; i<=n; i++){ [a, b] = [b, a+b]; } return n <= 2 ? n : b; }

6. 算法扩展与变种思考

6.1 变化步数场景

如果每次可以爬1、2或3阶，解法只需要修改状态转移方程：

def climb_stairs(n): if n <= 2: return n dp = [0]*(n+1) dp[0], dp[1], dp[2] = 1, 1, 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] return dp[n]

6.2 带限制条件的情况

考虑这些实际场景：

某些台阶损坏不能踩（需要增加判断条件）
连续跨2步不能超过3次（需要增加状态维度）
不同台阶有不同的体力消耗（引入最小值计算）

比如处理损坏台阶：

def climb_stairs(n, broken): dp = [0]*(n+1) dp[0] = 1 for i in range(1, n+1): if i in broken: continue dp[i] = dp[i-1] + (dp[i-2] if i>=2 else 0) return dp[n]