LeetCode 补充题 107. 任意步长的爬楼梯方案数
题目描述
[!green]
牛客原题： ✅ 补充题 107. 任意步长的爬楼梯方案数
一只青蛙需要跳上
n级台阶。每次可以向上跳任意正数级台阶，但所有跳跃的级数之和必须恰好为n。返回不同的跳法数量。跳跃顺序不同，视为不同的方案。
示例 1：
输入：
n = 3
输出：4
解释： 四种跳法为 1+1+1、1+2、2+1、3。
提示：
-
1≤n≤20。 - 每次可以跳任意正数级，但总跳跃级数必须恰好为
n。 - 跳跃顺序不同算不同方案。
题意分析
一种跳法可以写成总和为
n的有序正整数序列。题目允许任意正数步长，所以限制只有总长度，不需要像一次只能跳一两级那样逐级递推。将这段总长度划分成若干连续块，每块长度就是一次跳跃。问题因此转化为选择哪些位置作为相邻两次跳跃的分界。
解法：枚举单位台阶之间的断点
核心思路
[!blue]
将
n个单位台阶排成一行，内部恰好有n - 1个缝隙。每个缝隙独立选择断开或不断开；首尾不需要额外选择，每块至少包含一个单位，因此跳长始终为正。任意断点集合唯一确定各块长度，也就唯一确定跳跃序列；反过来，任意合法跳跃序列都能还原它的断点集合。因此两者一一对应，方案数为 $2^{n-1}$。
n = 1时没有缝隙，但空的断点集合仍对应直接跳一级这一种方案。题面限制n <= 20，可以直接用1 << (n - 1)计算，结果不会溢出。
解题步骤
- 把 n 个单位台阶排成一行，两个相邻单位之间共有 n-1 个缝隙。
- 每个缝隙独立选择断开或不断开，连续块的长度就是一次跳长。
- 在 n≤20 的约定下，用 1«(n-1) 返回方案数。
代码实现
class Solution {
public int jumpFloorII(int n) {
return 1 << (n - 1);
}
}
func jumpFloorII(n int) int {
return 1 << (n - 1)
}
复杂度分析
- 时间复杂度：$O(1)$，执行一次整数移位。
- 空间复杂度：$O(1)$，没有额外状态数组。
关键点总结
[!green]
断点集合与有顺序跳长序列一一对应，n=1 时没有缝隙，仍有一种跳法。
易错点总结
[!yellow]
不是只能跳1或2级的斐波那契题；不能将该位移公式直接用于任意大n。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 原题只允许 1 或 2 步，本题允许任意正跳长，因此从斐波那契递推变成全部断点组合。 |
| 377. 组合总和 Ⅳ | 中等 | 都是有顺序的正整数组成，本题所有正跳长都可选，所以存在闭式计数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！