LC70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 提示： 1 <= n <= 45

题目解析

题目在说什么

这道题其实是在问：你要爬一个楼梯，楼梯有 n 级台阶。每次你可以选择爬 1 级，或者爬 2 级。问：爬到楼顶（也就是第 n 级）一共有多少种不同的爬法？

比如楼梯有 2 级，你可以：

• 一次爬 1 级，再爬 1 级（共两步）
• 一次直接爬 2 级（一步到位）

所以答案是 2 种。

如果是 3 级，你可以：

• 1+1+1
• 1+2
• 2+1

一共 3 种。

注意：顺序不同也算不同的方法，比如 1+2 和 2+1 是两种。

思路是怎么来的

想象你站在楼梯前，要上第 n 级台阶。你最后一步是怎么上去的？只有两种可能：

1. 你从第 n-1 级台阶，再爬 1 级上来。 2. 你从第 n-2 级台阶，再爬 2 级上来。

所以，到达第 n 级的方法数，就等于“到达第 n-1 级的方法数”加上“到达第 n-2 级的方法数”。

为什么？因为最后一步只能是这两种选择，而且这两种选择不会重叠（你不可能同时从两个地方上来）。所以把它们加起来就是所有可能。

这就得到了一个递推关系：

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

其中 f(n) 表示爬到第 n 级的方法数。

那 f(1) 和 f(2) 是多少呢？

• 爬到第 1 级：只有一种方法，就是爬 1 级。所以 f(1)=1。
• 爬到第 2 级：可以一次爬 1 级再爬 1 级，或者一次爬 2 级。所以 f(2)=2。

有了这个递推公式和初始值，我们就可以从 f(1)、f(2) 开始，一步步算出 f(3)、f(4)……直到 f(n)。

这个思路和“斐波那契数列”很像，只是初始值不同（斐波那契是 f(1)=1, f(2)=1）。

代码逐步拆解

参考代码给出了三种写法，但核心思想一样。我们重点看第三种（也是最终版本），它最容易理解。

class Solution {
    int[] memo;  // 用来记录已经算过的结果，避免重复计算
    public int climbStairs(int n) {
        if (n == 1) return 1;   // 特殊情况：只有1级台阶
        if (n == 2) return 2;   // 特殊情况：只有2级台阶

        memo = new int[n + 1];  // 创建一个数组，下标从0到n，我们只用1到n
        memo[1] = 1;            // 初始值：爬到第1级有1种方法
        memo[2] = 2;            // 初始值：爬到第2级有2种方法

        // 从第3级开始，一直算到第n级
        for (int i = 3; i <= n; i++) {
            // 递推公式：f(i) = f(i-1) + f(i-2)
            memo[i] = memo[i - 1] + memo[i - 2];
        }

        return memo[n];  // 返回第n级的结果
    }
}

逐行解释：

• int[] memo; 声明一个数组，用来存储已经算好的结果。比如 memo[3] 就表示爬到第 3 级有多少种方法。
• if (n == 1) return 1; 如果楼梯只有 1 级，直接返回 1，不用往下算了。
• if (n == 2) return 2; 如果楼梯只有 2 级，直接返回 2。
• memo = new int[n + 1]; 创建数组，大小是 n+1，这样下标就可以从 0 到 n。我们只用到 1 到 n。
• memo[1] = 1; 设置初始值：爬到第 1 级有 1 种方法。
• memo[2] = 2; 设置初始值：爬到第 2 级有 2 种方法。
• for (int i = 3; i <= n; i++) 从第 3 级开始，一直算到第 n 级。