108.爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

• 输入：n = 2
• 输出：2
• 解释：有两种方法可以爬到楼顶。
  • 1. 1 阶 + 1 阶
  • 2. 2 阶

示例 2：

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

提示：

• • 1 <= n <= 45

思路

从最后一步倒着想

假设你要爬到第n级台阶，想一想你的最后一步是怎么走的:

• 要么从第n-1级跨1步上来
• 要么从第n-2级跨2步上来

所以，爬到第n级的方法数 = 爬到第 n-1 级的方法数 + 爬到第 n-2 级的方法数。

这就形成了一个递推关系:

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

其中f(1) =1 (只有1种方法爬到第1级)，f(2) = 2 (1+1或2)

这个数列其实就是斐波那契数列（从 1, 2 开始）。

举例：从底层往上推 - f(1) = 1 - f(2) = 2 - f(3) = f(2) + f(1) = 2 + 1 = 3 - f(4) = f(3) + f(2) = 3 + 2 = 5 - f(5) = f(4) + f(3) = 5 + 3 = 8

解法一： 递归(最直观、最慢)

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}

缺点：重复计算太多，时间复杂度 O(2ⁿ)，n 稍大就会超时。

解法二: 动态规划(用数组记录)

用一个数组 dp 保存已经算过的结果，避免重复计算：

class Solution {
    fun climbStairs(n: Int): Int {
        // n = 1 时，只有一种走法
        if (n <= 1) return 1

        // dp[i] 表示走到第 i 级台阶，有多少种走法
        val dp = IntArray(n + 1)

        // 第 1 级台阶：只有一种走法
        dp[1] = 1

        // 第 2 级台阶：两种走法
        // 1 + 1
        // 2
        dp[2] = 2

        // 从第 3 级开始，每一级都等于前两级之和
        for (i in 3..n) {
            // 到第 i 级的方法数
            // = 从第 i-1 级走 1 步上来
            // + 从第 i-2 级走 2 步上来
            dp[i] = dp[i - 1] + dp[i - 2]
        }

        return dp[n]
    }
}

解法三： 滚动数组(空间优化)

其实我们只需要记住前两个值，不需要整个数组： 滚动数组的本质就是： 既然 dp[i] 只用到 dp[i-1] 和 dp[i-2]，那就没必要把整个数组都存下来，只保留前两个数就行。

class Solution {
    fun climbStairs(n: Int): Int {
        // n = 1 时，只有 1 种走法
        if (n <= 1) return 1

        // a 表示 dp[i - 2]
        // b 表示 dp[i - 1]
        var a = 1
        var b = 2

        // 从第 3 级开始往后推
        for (i in 3..n) {
            // 当前台阶的方法数
            val c = a + b

            // 往前滚动一格：
            // a 变成原来的 b
            // b 变成当前算出来的 c
            a = b
            b = c
        }

        return b
    }
}

复杂度

• 时间复杂度: 时间 O(n)
• 空间复杂度: 空间 O(1)

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!