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

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

想象你面前有一座 10 层的楼梯，每次可以选择跨 1 级或 2 级台阶。这个问题看似简单，却蕴含着重要的算法思想。

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

• 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 时计算量已经无法接受。

3. 动态规划的核心思想

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

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

对于爬楼梯问题，状态转移方程为 dp[n] = dp[n-1] + dp[n-2]。