LeetCode 70. 爬楼梯

约 4 分钟
文章信息 29 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 100-200 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 小米 百度 网易 快手 滴滴 携程 B站 虾皮 贝壳 深信服 新浪 猿辅导 作业帮
标签
动态规划 数学 记忆化

题目描述

✅ 70. 爬楼梯

image-20260928190453578

题意分析

从第 0 阶出发，每次向上爬 1 阶或 2 阶，统计恰好到达第 n 阶的不同走法数。必须刚好到达，不能越过楼顶；每次跨几阶的先后顺序不同，就算不同走法。

题目要求方案总数，无需输出每条路线，也不是求最少爬几次。输入范围为 1 <= n <= 45，答案可以用 32 位有符号整数保存。

解法：滚动变量动态规划

核心思路

[!blue]

直接枚举所有路线会反复计算到达同一阶的走法。我们只需要知道每一阶有多少种走法，因此定义 dp[i] 为恰好到达第 i 阶的方案数。

按最后一步分类：如果最后跨 1 阶，之前必须到达第 i - 1 阶，每条到达该阶的路线都可以唯一地接上这一步，共有 dp[i - 1] 种；如果最后跨 2 阶，同理共有 dp[i - 2] 种。

这两类路线的最后一步不同，不会重复；每条合法路线的最后一步又只能属于其中一类，不会遗漏。因此从第 3 阶开始，有 dp[i] = dp[i - 1] + dp[i - 2]。

边界为 dp[1] = 1、dp[2] = 2：到第 1 阶只能跨一步，到第 2 阶可以连续跨两次 1 阶，也可以直接跨 2 阶。按阶数递增计算时，每个新状态依赖的两个状态都已经得到。

由于之后只会用到最近两阶，不必保存整个 dp 数组。每轮开始时，preTwo 表示 dp[step - 2]，preOne 表示 dp[step - 1]；先用它们求出 cur = dp[step]，再把两个变量向前推进一阶。处理完第 n 阶后，preOne 就是答案。

解题步骤

  1. n <= 2 时直接返回 n，处理不需要递推的边界。
  2. 令 preTwo = 1、preOne = 2，分别保存第 1、2 阶的方案数。
  3. 从 step = 3 遍历到 n，先计算 cur = preOne + preTwo，再令 preTwo = preOne、preOne = cur。
  4. 循环结束时已计算完第 n 阶，返回 preOne。

代码实现

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int preTwo = 1;
        int preOne = 2;

        for (int step = 3; step <= n; step++) {
            // 前一级与前两级的方案数相加，先得到新状态再推进两个旧状态。
            int cur = preOne + preTwo;

            preTwo = preOne;
            preOne = cur;
        }

        return preOne;
    }
}

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    preTwo := 1
    preOne := 2
    for step := 3; step <= n; step++ {
        // 前一级与前两级的方案数相加，先得到新状态再推进两个旧状态。
        cur := preOne + preTwo
        preTwo = preOne
        preOne = cur
    }

    return preOne
}

复杂度分析

  • 时间复杂度：$O(n)$，每一阶只计算一次。
  • 空间复杂度：$O(1)$，只保留前两个状态。

关键点总结

[!green]

  • 按最后一步是 1 阶还是 2 阶分类，两类方案互斥且完整。
  • 初值必须和下标对应；本实现从第 3 阶开始递推，所以保存的是第 1、2 阶的方案数 1、2。
  • 更新滚动变量时要保留旧值，避免覆盖仍需参与计算的状态。

易错点总结

[!yellow]

  • 未单独处理 n = 1，会错误返回第 2 阶的初值 2。
  • 循环从第 2 阶开始或使用 < n，会多算或少算一轮。
  • 先覆盖 preOne 再赋给 preTwo，会丢失旧状态。
  • 只统计跨 1 阶和跨 2 阶各用了多少次，会把不同先后顺序合并，漏掉合法方案。

相似题目

题目 难度 关联与区别
746. 使用最小花费爬楼梯 简单 移动步数仍为1或2，原题最小化费用，本题统计不同走法。
1137. 第 N 个泰波那契数 简单 同样根据有限个前项滚动递推，原题依赖前三项，本题依赖前两项。
91. 解码方法 中等 按最后一段长度递推前缀方案数；本题最后一步可跨一阶或两阶，该题最后编码可占一位或两位。
补充题 107. 任意步长的爬楼梯方案数 简单 每次可以跳任意正数级，而不是只跳1级或2级。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/77096845
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！