C语言实战：从爬楼梯问题解析动态规划的核心思想

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

想象你面前有一座10层的楼梯，每次可以选择跨1级或2级台阶。这个问题看似简单，却蕴含着重要的算法思想。我第一次遇到这个问题时，第一反应是用穷举法列出所有可能，但当台阶数增加到20级时，组合数量已经爆炸性增长，这时候才意识到需要更聪明的解法。

让我们从小规模案例入手：

• 1级台阶：只有1种方法（跨1步）
• 2级台阶：2种方法（1+1或直接跨2步）
• 3级台阶：3种方法（1+1+1，1+2，2+1）

你会发现一个规律：到达第n级台阶的方法数，等于到达(n-1)级和(n-2)级方法数的和。这是因为最后一步要么是从n-1级跨1步，要么是从n-2级跨2步。

2. 递归解法及其局限性

最直观的解法是递归：

int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n-1) + climbStairs(n-2); } 

但这种方法存在严重问题：重复计算。比如计算climbStairs(5)时需要计算climbStairs(3)和climbStairs(4)，而climbStairs(3)又会被重复计算多次。时间复杂度是指数级的O(2^n)，当n=40时计算量已经无法接受。

我在实际测试中发现，递归解法在n=45时需要近10秒才能得出结果，而优化后的动态规划解法只需不到1毫秒。

3. 动态规划的核心思想

动态规划通过存储中间结果来避免重复计算，包含三个关键要素：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 边界条件：最小子问题的解
3. 状态转移方程：如何由子问题的解得到更大问题的解

对于爬楼梯问