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

📌 题目描述

题目级别：简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

💡 解题思路：动态规划 (Dynamic Programming)

这道题是学习动态规划的完美起点。我们可以通过推导发现其中的规律：

• 爬到第 1 阶，只有 1 种方法（爬 1 阶）。
• 爬到第 2 阶，有 2 种方法（爬 1+1 阶，或者直接爬 2 阶）。
• 那么爬到第 i 阶呢？ 由于每次只能爬 1 阶或 2 阶，所以到达第 i 阶的最后一步，只有两种可能：
  1. 从第 i-1 阶跨 1 步上来。
  2. 从第 i-2 阶跨 2 步上来。

因此，到达第 i 阶的总方法数，等于到达 i-1 阶的方法数，加上到达 i-2 阶的方法数。
这就得到了动态规划中最核心的状态转移方程：

f[i] = f[i - 1] + f[i - 2]

这其实就是一个斐波那契数列！

🚀 解法一：一维数组记录状态 (空间 O(N))

这是最直观的写法，我们开辟一个长度为 $N+1$ 的数组，把到达每一阶的方法数都存下来。

💻 C++ 代码实现

class Solution {
public:
    int climbStairs(int n) {
        // 因为 n 最小为 1，为了防止越界，特判一下
        if (n <= 2) return n; 

        // 开辟数组记录状态
        int f[50]; 
        f[1] = 1;
        f[2] = 2;

        // 从第 3 阶开始递推
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 2] + f[i - 1];
        }

        return f[n];
    }
};

🏆 解法二：滚动变量空间优化 (空间 O(1) 面试最优解)

在解法一中，我们使用了一个数组来记录所有台阶的方法数。但是仔细观察状态转移方程 f[i] = f[i - 1] + f[i - 2]，你会发现：计算当前台阶的方法数，仅仅依赖于它前面的两个台阶！

既然如此，我们完全不需要记住前面所有的历史记录。我们只需要用两个变量，交替记录“前一个”和“前两个”台阶的方法数就可以了。这种技巧在动态规划中被称为滚动数组 / 滚动变量。

💻 进阶 C++ 代码实现

class Solution {
public:
    int climbStairs(int n) {
        // 边界条件特判
        if (n <= 2) return n;

        int prev2 = 1; // 相当于 f[i-2]，初始化为到达第 1 阶的方法数
        int prev1 = 2; // 相当于 f[i-1]，初始化为到达第 2 阶的方法数
        int curr = 0;  // 相当于 f[i]，记录当前到达第 i 阶的方法数

        for (int i = 3; i <= n; i++) {
            curr = prev1 + prev2; // 当前等于前两项之和
            
            // 变量滚动，为下一次循环做准备
            prev2 = prev1; 
            prev1 = curr;  
        }

        return curr;
    }
};