LeetCode 剑指 Offer 10- II. 青蛙跳台阶问题

约 5 分钟
文章信息 20 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 美团 阿里巴巴 快手 腾讯 百度 滴滴 京东 华为 网易 小米 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
动态规划 数学 动态规划经典题 记忆化搜索
目录

题目描述

✅ 剑指 Offer 10- II. 青蛙跳台阶问题

image-20250510210933309

image-20241107204506727

题意分析

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶，问跳上一个 n 级台阶总共有多少种跳法。要求的是「方案数」，不是最少步数，也不是具体的跳法序列，所以每一种落脚点的先后顺序不同就算作不同方案。

顺序敏感这一点是理解题意的关键：先跳 1 级再跳 2 级，和先跳 2 级再跳 1 级，虽然用的台阶数一样，但算两种不同跳法。因此这不是「用 1 和 2 凑出 n 的组合数」，而是「有序序列」的计数。

题目明确要求答案对 1000000007 取模。这个信号说明真实方案数会随 n 增长到极大，n 取到上限时早已超出 64 位整数的表示范围，所以取模不是收尾动作，而是必须贯穿整个计算过程的约束。

数据范围是 0 <= n <= 100，注意下界是 0 而不是 1。n = 0 表示台阶数为零，青蛙什么都不用跳就已经站在终点，题目约定这算作一种跳法，答案是 1 而不是 0。这条约定是本题最容易被忽略的边界，也是它和常规爬楼梯题的差别所在。

其余边界很简单：n = 1 只有「跳 1 级」一种；n = 2 有「1 + 1」和「2」两种。这三个值一起构成了递推的起点和验证基准。

解法：滚动变量动态规划

核心思路

问题关键：若枚举所有跳法，每一级都会分成“跳 1 级”和“跳 2 级”，产生指数级递归树。不同路径到达同一级后，剩余问题完全相同，因此应把“到达某一级的方案数”作为状态。

定义 ways[i] 为跳上 i 级台阶的方案数。按最后一步分类：最后跳 1 级的方案来自 i - 1，最后跳 2 级的方案来自 i - 2；两类互斥且覆盖全部情况，因此

\[ways[i] = ways[i - 1] + ways[i - 2]\]

边界是 ways[0] = 1、ways[1] = 1。ways[0] = 1 表示“不跳”这一种空方案，这一点与标准斐波那契的 F(0) = 0 不同。

为什么选滚动 DP：当前状态只依赖前两项，用 a、b 分别保存相邻状态即可。第 i 轮开始前保持不变量 a = ways[i]、b = ways[i + 1]；更新 (a,b) = (b,a+b) 后，不变量推进到下一轮。执行 n 轮后，a = ways[n]。

正确性：每个合法方案的最后一步只能是 1 或 2，这两类既无重复也无遗漏；递推式因此正确。初值覆盖 n = 0,1，滚动更新又与递推式完全一致，所以由归纳法可得最终答案。每步取模利用加法的同余性质，不改变最终模值。

解题步骤

面试时可按下面 4 步口述：

  1. 用“最后一步”推导出 ways[i] = ways[i - 1] + ways[i - 2]。
  2. 初始化 a = 1、b = 1，对应 ways[0]、ways[1]。
  3. 循环 n 次，每轮计算下一项并把窗口右移，同时对 1000000007 取模。
  4. 返回 a，它此时表示 ways[n]。

例如 n = 4，(a,b) 依次为 (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8)，最终返回 5。n = 0 时循环不执行，返回空跳法数量 1。

代码实现

class Solution {
    private static final int MOD = 1000000007;

    public int numWays(int n) {
        int a = 1;
        int b = 1;
        for (int i = 0; i < n; i++) {
            int sum = (a + b) % MOD;
            a = b;
            b = sum;
        }
        return a;
    }
}

func numWays(n int) int {
    const mod = 1000000007
    a, b := 1, 1
    for i := 0; i < n; i++ {
        a, b = b, (a+b)%mod
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(n)$。每一级只递推一次。
  • 空间复杂度：$O(1)$。只保存相邻两个状态。

关键点总结

  • 计数类 DP 可优先按“最后一步”分类，确认各类互斥且穷尽后再相加。
  • ways[0] = 1 是递推成立的边界，不能照搬标准斐波那契初值。
  • 只依赖前两项，无需数组；循环不变量能同时说明更新逻辑与返回值。
  • 模运算应放进每轮递推，避免中间值溢出。

易错点总结

  • 把 ways[0] 写成 0 会使整条序列错位；本题中“不跳”也算一种方案。
  • 把跳法当成无序组合会漏解：1 + 2 与 2 + 1 是两种不同顺序。
  • 只在返回时取模无法补救此前的整数溢出，必须每次相加后立即取模。
  • Java 更新时若先覆盖 a 或 b，会丢失上一轮状态；先计算 sum 再整体右移。
  • 本模板循环 n 次并返回 a，不要与“从 i = 2 开始、返回后一项”的模板混用。

相似题目

题目 难度 考察点
70. 爬楼梯 简单 完全同款递推，但无需取模，且 n 从 1 起
509. 斐波那契数 简单 标准斐波那契，初值为 f(0) = 0，正好对照本题的偏移
746. 使用最小花费爬楼梯 简单 从计数改为求最值，转移由求和变成取 min 并加上台阶代价
LCR 088. 使用最小花费爬楼梯 简单 上一题的 LCR 版本，可用来复核起点可选两处的边界处理
剑指 Offer 10- I. 斐波那契数列 简单 同样取模但初值不同，最适合检验是否真的记住了边界差异
面试题 08.01. 三步问题 简单 步长扩展到 1、2、3，转移变成三项相加，需维护三个变量
1137. 第 N 个泰波那契数 简单 三项递推的纯净版，用来练滚动三变量的右移顺序