从递归到滚动数组：爬楼梯问题的四种解法演进与实战剖析
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]7. 实战应用与算法思维
这个问题的解法演进展示了算法优化的典型路径：
- 暴力递归（明确问题可分解）
- 记忆化搜索（消除重复计算）
- 标准动态规划（转为迭代）
- 空间优化（发现状态依赖规律）
在图像处理、金融建模等领域，类似的优化思路随处可见。比如图像分割中的动态规划算法，最初可能用递归实现，最终优化为迭代+滚动数组的形式。