动态规划入门：爬楼梯问题解法与优化

1. 爬楼梯问题概述

LeetCode第70题"爬楼梯"是动态规划领域的经典入门题目，题目描述很简单：假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法可以爬到楼顶？

这个问题看似简单，却蕴含着动态规划的核心思想。我第一次遇到这个问题时，直觉反应是用递归解决，但很快发现当n较大时递归效率极低。后来通过动态规划优化，将时间复杂度从O(2^n)降到了O(n)，这让我深刻理解了动态规划的价值。

2. 问题分析与解法思路

2.1 暴力递归解法

最直观的解法是递归：爬到第n阶的方法数等于爬到第n-1阶的方法数（最后一步爬1阶）加上爬到第n-2阶的方法数（最后一步爬2阶）。递归的终止条件是n=1时返回1，n=2时返回2。

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

这个解法虽然正确，但存在严重的效率问题。时间复杂度是指数级的O(2^n)，因为每次递归都会分裂成两个子问题。当n=40时，在我的机器上需要约5秒才能计算出结果，这在算法竞赛或面试中是完全不可接受的。

2.2 动态规划解法

动态规划通过存储中间结果避免了重复计算。我们可以创建一个数组dp，其中dp[i]表示爬到第i阶的方法数。根据问题描述，dp[i] = dp[i-1] + dp[i-2]。

cpp复制int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n+1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

这个解法的时间复杂度是O(n)，空间复杂度也是O(n)。在我的测试中，n=40时几乎瞬间就能得到结果，相比递归有了质的飞跃。

2.3 空间优化解法

观察上面的动态规划解法，我们发现计算dp[i]只需要dp[i-1]和dp[i-2]，因此可以进一步优化空间复杂度到O(1)。

cpp复制int climbStairs(int n) {
    if (n <= 2) return n;
    int prev1 = 1, prev2 = 2;
    for (int i = 3; i <= n; ++i) {
        int curr = prev1 + prev2;
        prev1 = prev2;
        prev2 = curr;
    }
    return prev2;
}

这个版本保留了O(n)的时间复杂度，但空间复杂度降到了O(1)，只使用了三个变量。在实际应用中，这种优化对于大规模问题尤为重要。

3. 数学原理深入解析

3.1 斐波那契数列关系

爬楼梯问题实际上是斐波那契数列的一个变种。斐波那契数列定义为F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)。而爬楼梯问题的解序列是1,2,3,5,8...，相当于斐波那契数列向后偏移一位。

理解这种关系有助于我们应用斐波那契数列的各种性质和解法。例如，我们可以使用矩阵快速幂或通项公式来将时间复杂度进一步降低到O(log n)。

3.2 通项公式解法

斐波那契数列的通项公式为：
F(n) = (φ^n - ψ^n)/√5，其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618

因此爬楼梯问题的解可以表示为：
climbStairs(n) = (φ^(n+1) - ψ^(n+1))/√5

cpp复制int climbStairs(int n) {
    double sqrt5 = sqrt(5);
    double phi = (1 + sqrt5) / 2;
    return (int)round(pow(phi, n + 1) / sqrt5);
}

这个解法的时间复杂度是O(1)，但由于浮点数精度问题，当n较大时可能会产生误差。在实际应用中，动态规划解法更为可靠。

4. 变种问题探讨

4.1 每次可以爬1、2或3阶

如果题目改为每次可以爬1、2或3阶，递推关系变为dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。初始条件需要调整为dp[1]=1，dp[2]=2，dp[3]=4。

cpp复制int climbStairs3(int n) {
    if (n <= 2) return n;
    if (n == 3) return 4;
    vector<int> dp(n+1);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    return dp[n];
}

4.2 有障碍物的爬楼梯问题

LeetCode第746题"最小花费爬楼梯"是另一个有趣的变种。在这个问题中，每个台阶都有一个cost值，求到达顶部的最小花费。

解法思路类似，但需要考虑花费因素：

cpp复制int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1);
    for (int i = 2; i <= n; ++i) {
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }
    return dp[n];
}

5. 实际应用与面试技巧

5.1 面试中的考察重点

爬楼梯问题常被用作面试题，主要考察以下几个方面：

1. 能否识别出这是动态规划问题
2. 能否从递归解法优化到动态规划
3. 能否进一步优化空间复杂度
4. 能否讨论时间/空间复杂度的权衡

在面试中，建议按照以下步骤解答：

1. 先提出递归解法并分析其缺点
2. 引入动态规划解法并分析改进
3. 讨论空间优化可能性
4. 如有时间，可以提及数学解法和变种问题

5.2 实际工程应用

虽然爬楼梯问题本身看似简单，但其背后的动态规划思想在工程中有广泛应用：

1. 路径规划问题
2. 资源分配问题
3. 序列比对算法
4. 金融领域的期权定价模型

理解这个简单问题的解法，有助于我们解决更复杂的实际工程问题。

6. 常见错误与调试技巧

6.1 边界条件处理

新手常见的错误包括：

1. 忽略n=0的情况（根据题目描述，n是正整数，可以忽略）
2. 混淆dp数组的索引（dp[1]对应第1阶，不是第0阶）
3. 初始条件设置错误（dp[1]=1, dp[2]=2）

调试时可以打印dp数组的值，验证前几项是否正确：

cpp复制for (int i = 1; i <= n; ++i) {
    cout << "dp[" << i << "] = " << dp[i] << endl;
}

6.2 空间优化时的变量更新顺序

在空间优化版本中，变量更新顺序很重要。错误的更新顺序会导致计算结果错误：

cpp复制// 错误写法：
prev2 = prev1 + prev2;
prev1 = prev2;  // 此时prev2已经是新值了

// 正确写法：
int curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;

6.3 大数溢出问题

当n较大时（如n=45），结果可能超过int的范围。可以使用long long类型避免溢出：

cpp复制long long climbStairs(int n) {
    if (n <= 2) return n;
    long long prev1 = 1, prev2 = 2;
    for (int i = 3; i <= n; ++i) {
        long long curr = prev1 + prev2;
        prev1 = prev2;
        prev2 = curr;
    }
    return prev2;
}

7. 性能测试与比较

为了比较不同解法的性能，我进行了以下测试（环境：Intel i7-9700K, 16GB RAM）：

测试结果表明，动态规划解法在性能上显著优于递归解法。虽然通项公式在理论上时间复杂度最优，但由于浮点数精度问题，在实际应用中动态规划更为可靠。

8. 扩展学习建议

要深入理解动态规划，我建议从以下几个方面继续学习：

1. 背包问题（0-1背包、完全背包）
2. 最长公共子序列/子串问题
3. 矩阵链乘法问题
4. 编辑距离问题
5. 股票买卖问题系列

对于数学爱好者，可以深入研究斐波那契数列的各种性质和应用，如：

1. 斐波那契堆数据结构
2. 黄金分割比的应用
3. 斐波那契数列与自然界的关系

在实际编程练习中，可以尝试LeetCode上的这些相关问题：

• 198. 打家劫舍
• 213. 打家劫舍 II
• 746. 使用最小花费爬楼梯
• 1137. 第 N 个泰波那契数