LeetCode 剑指 Offer 10- II. 青蛙跳台阶问题
题目描述
题意分析
青蛙从第
0级出发，每次只能向上跳1级或2级，求恰好到达第n级的不同跳法数量。跳跃的先后顺序不同就算不同方案，不是只统计两种步长各用了多少次。
n = 0时，不进行任何跳跃也算一种完成方式。按本题的返回要求，方案数需要对1000000007取模；返回的是方案数量，不是最少跳跃次数。
解法：滚动变量动态规划
核心思路
[!blue]
令
ways[i]表示恰好到达第i级的跳法数量。对于i >= 2，最后一跳只有两种情况：从第i - 1级跳一级，或从第i - 2级跳两级。任意到达对应前一位置的方案，都能追加这最后一跳得到一个完整方案；两类最后一步不同，不会重复，而且覆盖全部可能，所以ways[i] = ways[i - 1] + ways[i - 2]。初值为
ways[0] = 1、ways[1] = 1。零级的一种空方案，使“直接跳两级”也能由递推计入；如果把它当成零种，会漏掉这类从起点直接出发的方案。每项只依赖相邻的前两项，保存两个变量即可。执行了
i轮更新后，a表示ways[i]，b表示ways[i + 1]。先求两者之和得到再下一项，再把旧b移到a、把新值移到b，就保持了下一轮需要的状态。执行n轮后返回a，它恰好对应第n级。这里保存的都是方案数的余数。加法满足先取模再相加与最后取模等价，所以每轮都取模不会改变最终答案。两个状态都小于模数，它们相加也仍在 32 位有符号整数范围内；无需先算出可能很大的完整方案数。
解题步骤
- 设模数为
1000000007，初始化a = 1、b = 1，分别对应零级和一级的方案数。- 共执行
n轮，每轮先计算下一项(a + b) % MOD。- 将旧
b赋给a，再把刚算出的下一项赋给b；Go 的并行赋值会先计算右侧，因此同样保留了两个旧值。- 返回
a。零级时不进入循环，直接返回空方案数量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)$，执行
n次常数时间的滚动更新。- 空间复杂度：$O(1)$，只保存相邻两项及一次加法结果。
关键点总结
[!green]
- 按最后一跳的步长分类，得到不重复、不遗漏的计数递推。
- 零级不是零种方案，空方案是递推的必要边界。
- 明确第
i轮之后两个变量分别代表哪两项，才能确定循环次数和返回值。- 每轮对加法结果取模，既保持答案正确，也控制中间数值大小。
易错点总结
[!yellow]
- 沿用普通斐波那契的零初值，会把本题方案数整体算错；这里两个初值均为
1。- 忽略跳跃顺序，把相同步长数量视为同一方案，会漏掉不同的排列。
- 只在最后取模，无法修复递推中早已发生的整数溢出。
- Java 未先算新值就覆盖旧变量，会错误地重复使用同一个状态。
- 本实现更新
n轮后返回a，不能混用其他初始化方式对应的轮数和返回位置。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 746. 使用最小花费爬楼梯 | 简单 | 移动步数仍为1或2，原题最小化费用，本题统计不同走法。 |
| 1137. 第 N 个泰波那契数 | 简单 | 同样根据有限个前项滚动递推，原题依赖前三项，本题依赖前两项。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！