动态规划入门：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++) {