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

1. LeetCode 70. 爬楼梯 | C++ 动态规划入门与空间优化题解

1.1 题目描述与初步理解

这道题目描述非常简单：假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以选择爬1个台阶或者2个台阶。问有多少种不同的方法可以爬到楼顶？

我第一次看到这个题目时，觉得它像是一个排列组合问题。但当我尝试用n=3、n=4等小例子手动计算时，发现结果呈现出一个有趣的规律：

• n=1：只有1种方法（1）
• n=2：2种方法（1+1 或 直接2）
• n=3：3种方法（1+1+1，1+2，2+1）
• n=4：5种方法（1+1+1+1，1+1+2，1+2+1，2+1+1，2+2）

这个序列看起来很像斐波那契数列。这让我意识到，这可能不是一个简单的排列组合问题，而是一个可以用递归或动态规划解决的问题。

1.2 动态规划思路解析

动态规划(Dynamic Programming)是一种分阶段解决问题的方法。对于这道题，我们可以这样思考：

要到达第n阶楼梯，最后一步只有两种可能：

1. 从第n-1阶跨1步上来
2. 从第n-2阶跨2步上来

因此，到达第n阶的总方法数就是到达第n-1阶的方法数加上到达第n-2阶的方法数。这就是我们的状态转移方程：

f(n) = f(n-1) + f(n-2)

这个方程和斐波那契数列的定义完全一致。理解这一点是解决这个问题的关键。

注意：这里的状态转移方程是动态规划的核心。在实际面试中，面试官最看重的就是你能否正确推导出这个方程。

1.3 基础解法：使用数组存储中间状态

1.3.1 算法实现

最直观的实现方式是使用一个数组来存储每个台阶对应的方法数：

cpp复制class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n; // 边界条件处理
        
        int dp[n+1]; // 创建DP数组
        dp[1] = 1;   // 到达第1阶有1种方法
        dp[2] = 2;   // 到达第2阶有2种方法
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2]; // 状态转移
        }
        
        return dp[n];
    }
};

1.3.2 复杂度分析

• 时间复杂度：O(n)，因为我们需要计算从3到n的每一个台阶的方法数
• 空间复杂度：O(n)，因为我们需要存储n个中间结果

1.3.3 边界条件处理

在实际编码中，边界条件的处理非常重要。对于n=1和n=2的情况，我们直接返回n，因为：

• 到达第1阶只有1种方法
• 到达第2阶有2种方法（1+1或直接2）

如果不处理这些边界条件，当n=1时，dp[2]的访问会导致数组越界。

1.4 空间优化解法：滚动变量技巧

1.4.1 优化思路

观察状态转移方程f(n) = f(n-1) + f(n-2)，我们发现计算当前台阶的方法数只需要前两个台阶的方法数。这意味着我们不需要存储所有的中间结果，只需要保存最近的两个状态即可。

这种优化技巧在动态规划中被称为"滚动数组"或"滚动变量"技术，可以显著减少空间复杂度。

1.4.2 优化后的实现

cpp复制class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        
        int prev2 = 1; // 相当于f(n-2)
        int prev1 = 2; // 相当于f(n-1)
        int current = 0;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;
            // 更新前两个状态
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
};

1.4.3 复杂度分析

• 时间复杂度：仍然是O(n)，因为循环次数没有变化
• 空间复杂度：优化到O(1)，因为我们只使用了三个变量

提示：这种优化后的解法通常是面试官期望的最优解，因为它既保持了线性的时间复杂度，又将空间复杂度降到了常数级别。

1.5 递归解法及其问题

虽然这道题可以用递归解决，但我不推荐在实际中使用纯递归解法。原因如下：

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

这个递归解法虽然简洁，但存在严重的问题：

1. 时间复杂度是O(2^n)，因为每次调用会产生两个子调用
2. 存在大量重复计算，比如计算f(5)需要计算f(4)和f(3)，而f(4)又要计算f(3)和f(2)

可以通过记忆化搜索(Memoization)来优化递归解法，但即便如此，递归调用栈的空间开销仍然存在。因此，对于这个问题，迭代的动态规划解法是更好的选择。

1.6 数学解法：通项公式

有趣的是，这个问题还可以用数学方法解决。因为爬楼梯问题等价于斐波那契数列，而斐波那契数列有通项公式：

f(n) = (φ^n - ψ^n)/√5，其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618

因此可以写出O(1)时间复杂度的解法：

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

不过在实际编程中，这种方法有几个问题：

1. 浮点数运算可能存在精度问题，特别是当n较大时
2. 对于编程面试来说，面试官通常期望看到动态规划的解法
3. 这种方法虽然时间复杂度低，但可读性和可维护性较差

1.7 常见问题与调试技巧

1.7.1 数组越界问题

在实现基础解法时，新手常犯的错误是忘记处理边界条件。例如：

cpp复制int dp[n+1];
dp[1] = 1;
dp[2] = 2;
// 如果n=1，这里访问dp[2]就会越界

解决方法：在开始前先检查n的值，如果n<=2直接返回n。

1.7.2 变量初始化错误

在滚动变量解法中，容易混淆prev1和prev2的初始值。记住：

• prev2对应f(1)=1
• prev1对应f(2)=2

1.7.3 循环起始点错误

循环应该从i=3开始，因为f(1)和f(2)已经作为初始条件给出。如果从i=2开始，会导致逻辑错误。

1.7.4 大数问题

当n比较大时（比如n=45），结果可能会超过int的范围。在C++中，可以使用long long来存储中间结果：

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

1.8 实际应用与变种问题

爬楼梯问题虽然简单，但它体现了动态规划的核心思想，是理解更复杂DP问题的基础。在实际中，类似的思想可以应用于：

1. 路径规划问题
2. 投资组合优化
3. 资源分配问题

常见的变种问题包括：

1. 每次可以爬1、2或3个台阶
2. 某些台阶不能踩（需要跳过）
3. 每次爬的台阶数是一个集合中的任意元素（如{1,3,5}）

例如，如果每次可以爬1、2或3个台阶，状态转移方程就变为：
f(n) = f(n-1) + f(n-2) + f(n-3)

1.9 个人经验与建议

在刷题和面试过程中，我有以下几点经验分享：

1. 从小例子入手：当遇到DP问题时，先用手动计算小例子（n=1,2,3,4）来寻找规律。

2. 明确状态定义：清楚地定义dp[i]表示什么。在这个问题中，dp[i]表示到达第i阶楼梯的方法数。

3. 画状态转移图：对于复杂的DP问题，画出状态之间的转移关系可以帮助理解。

4. 先写基础解法再优化：面试时，可以先给出O(n)空间的解法，然后自然地过渡到优化版本，展示你的思考过程。

5. 注意边界条件：DP问题往往有简单的边界条件，但容易被忽略。养成先考虑边界情况的习惯。

6. 测试用例设计：验证你的代码时，至少要测试以下情况：

   • n=0（如果题目允许）
   • n=1
   • n=2
   • n=较大的值（如10）

1.10 进一步学习资源

如果你想更深入地学习动态规划，我推荐以下资源：

1. 《算法导论》中的动态规划章节
2. LeetCode上的DP专题
3. 经典的DP问题：背包问题、最长公共子序列、编辑距离等
4. 在线算法课程中的DP模块

记住，掌握动态规划需要大量的练习。从简单的问题（如爬楼梯）开始，逐步挑战更复杂的问题，是学习DP的有效路径。