70. 爬楼梯#

记得刚开始学编程时，看到动态规划这三个字就头大。直到遇到了 LeetCode 70 题「爬楼梯」，它就像一把打开动态规划大门的钥匙，让我对这个算法思想有了全新的认识。今天，让我们一起通过这道题，揭开动态规划的神秘面纱。

🎯 问题本质：生活中的场景#

想象你正在爬楼梯，每次可以爬1步或2步。给定一个楼梯的总阶数n，你想知道有多少种不同的爬法。比如：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶
1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

plaintext

看起来很简单对吧？但这道题蕴含着动态规划最核心的思想。

问题描述#

题目目标#

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

示例 1#

输入： n = 3 输出： 3 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 从递归到动态规划：思维的蜕变#

让我们像孩子学走路一样，一步步理解这个问题：

第一步：递归的直觉#

站在第n级台阶上，我们是怎么到达这里的？

要么从第(n-1)级跨了1步上来
要么从第(n-2)级跨了2步上来

这就意味着：到达第n级的方法数 = 到达第(n-1)级的方法数 + 到达第(n-2)级的方法数

这是不是让你想起了什么？没错，斐波那契数列！

第二步：发现重叠子问题#

如果我们直接用递归实现：

// 方法一：朴素递归（会超时）
class Solution {
    public int climbStairs(int n) {
        // 边界情况：当台阶数为 1 或 2 时，方案数分别就是 1 或 2
        if (n <= 2) return n;
        // 递归公式：到第 n 阶的方法数 = 到第 n-1 阶的方法数 + 到第 n-2 阶的方法数
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

// 方法二：记忆化递归
class Solution {
    // memo[i]：缓存“到达第 i 阶”的方案数，避免重复递归计算
    private int[] memo;

    public int climbStairs(int n) {
        // 创建记忆数组，下标范围是 0..n，所以长度为 n+1
        memo = new int[n + 1];
        // 从目标台阶 n 开始递归求解
        return climb(n);
    }

    private int climb(int n) {
        // 递归终止条件：n 为 1 或 2 时直接返回已知答案
        if (n <= 2) return n;
        // 若该状态已经算过，直接返回缓存值
        if (memo[n] != 0) return memo[n];
        // 计算当前状态并写入缓存：f(n) = f(n-1) + f(n-2)
        memo[n] = climb(n-1) + climb(n-2);
        // 返回当前台阶的方案数
        return memo[n];
    }
}

// 方法三：动态规划（最终优化版本）
class Solution {
    public int climbStairs(int n) {
        // 边界情况：n 为 1 或 2 时无需进入循环，直接返回
        if (n <= 2) return n;

        int prev2 = 1;  // prev2 保存“前前一阶”的方案数，即 dp[i-2]
        int prev1 = 2;  // prev1 保存“前一阶”的方案数，即 dp[i-1]
        int current = 0; // current 保存“当前阶 i”的方案数，即 dp[i]

        for (int i = 3; i <= n; i++) {
            // 状态转移：到第 i 阶的方案数 = 到第 i-1 阶 + 到第 i-2 阶
            current = prev1 + prev2;
            // 变量滚动：原来的 dp[i-1] 变成下一轮的 dp[i-2]
            prev2 = prev1;
            // 变量滚动：原来的 dp[i] 变成下一轮的 dp[i-1]
            prev1 = current;
        }

        // 循环结束后，current 就是到达第 n 阶的总方案数
        return current;
    }
}

java

看到递归代码的那一刻，你可能会想：“这不就结了吗？“但等你实际运行，就会发现性能惨不忍睹。为什么？

画出递归树，你会发现大量的重复计算。比如计算f(5)时，f(3)会被重复计算多次。这就是动态规划中最关键的概念之一：重叠子问题。

第三步：优化的艺术#

发现重复计算后，我们自然会想到用一个数组把计算过的结果存起来，这就是”记忆化”技术。但还能更好吗？

仔细观察发现，我们其实只需要保存前两个状态就够了！这就引出了动态规划最精髓的地方：状态转移。

🔍 动态规划的四个核心要素#

通过爬楼梯这个例子，我们可以总结出动态规划的核心要素：

找到状态定义：dp[i]表示爬到第i级台阶的方法数
确定状态转移方程：dp[i] = dp[i-1] + dp[i-2]
明确初始状态：dp[1] = 1, dp[2] = 2
确定计算顺序：从小到大递推

这四个要素，就像盖房子的地基、墙壁、屋顶和施工顺序，缺一不可。

🎯 举一反三#

理解了爬楼梯，你就掌握了动态规划的入门钥匙。类似的题目还有：

打家劫舍（House Robber）
最大子数组和（Maximum Subarray）
买卖股票的最佳时机（Best Time to Buy and Sell Stock）

它们都遵循相似的思维模式：寻找状态定义→推导转移方程→优化空间复杂度。

💡 思考题#

如果我们改变规则：可以爬1、2或3步，代码该如何修改？这种情况下，空间优化还能实现吗？

🎓 面试技巧#

面试中遇到动态规划的题目，建议这样展示你的思路：

先说明问题的特征 - 最优子结构和重叠子问题。然后从最简单的递归解法开始，一步步优化到动态规划。这样不仅展示了你解决问题的能力，还体现了你对性能优化的理解。

记住，动态规划不是一个神秘的算法，而是一种解决问题的思维方式。它教会我们如何把大问题分解成小问题，并通过存储中间结果来提高效率。

动态规划不难，难的是养成动态规划的思维方式。希望这篇文章能帮助你打开思路，在算法之路上更进一步！