每步可走 1/2/3 个台阶,N 个台阶共有多少种走法。
一共有 N 个台阶,每步可以走 1 个、2 个或 3 个台阶。求走完 N 个台阶共有多少种不同的方案。
f[N] = f[N−1] + f[N−2] + f[N−3]。递推最后一步划分三项斐波那契边界处理
| 项目 | 说明 |
|---|---|
| 输入 | 一个整数 N |
| 输出 | 走法的总数 |
| 数据范围 | 1 ≤ N ≤ 60 |
| 每步选择 | 1、2 或 3 个台阶 |
| 方案区分 | 按"每步走多少"的序列区分 |
f[0] = 1(0 级台阶只有"什么都不走"1 种)、f[1] = 1、f[2] = 2先按递推算,再手工枚举核对。
f[0] = 1(一级都不走,也只有这一种"走法")
f[1] = 1(只能一次走 1 级)
f[2] = 2(1+1 或 一次走 2 级)
f = [1, 1, 2, …]
f[3] = f[2] + f[1] + f[0] = 2 + 1 + 1 = 4
f[4] = f[3] + f[2] + f[1] = 4 + 2 + 1 = 7
f[4] = 7
| 序号 | 走法(每步台阶数) | 步数 |
|---|---|---|
| 1 | 1 + 1 + 1 + 1 | 4 |
| 2 | 1 + 1 + 2 | 3 |
| 3 | 1 + 2 + 1 | 3 |
| 4 | 2 + 1 + 1 | 3 |
| 5 | 1 + 3 | 2 |
| 6 | 3 + 1 | 2 |
| 7 | 2 + 2 | 2 |
共 7 种 ✓ 与递推一致
1+3 和 3+1 是两种方案,因为它们每一步的走法序列不同。这与"只问用了几步"的问题完全不同——读题时要看清"方案"的定义。继续把递推表算下去。
| N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| f[N] | 1 | 1 | 2 | 4 | 7 | 13 | 24 | 44 | 81 | 149 | 274 |
f[10] = 274 ✓ 与样例一致
f[5] = f[4]+f[3]+f[2] = 7+4+2 = 13 ✓
f[6] = 13+7+4 = 24 ✓
f[7] = 24+13+7 = 44 ✓
f[8] = 44+24+13 = 81 ✓
f[9] = 81+44+24 = 149 ✓
f[10] = 149+81+44 = 274 ✓
全部吻合
f[60] 约为 7 × 10¹⁵,恰好超出 int(约 2.1 × 10⁹)但仍在 long long 内——这也是题目把 N 限制在 60 的原因之一。f[i] = f[i−1] + f[i−2] + f[i−3]
递归生成所有"每步走几级"的序列
| 方案 | 复杂度(N = 60) | 可行性 |
|---|---|---|
| 线性递推 | 60 次加法 | ✅ 瞬间 |
| 搜索枚举 | 约 7 × 10¹⁵ 种 | ❌ 不可行 |
输入台阶数 N,程序会递推给出方案数并展示每一步的值。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long f[70]; int main() { int N; scanf("%d", &N); f[0] = 1; // 0 级台阶:只有"不走"1 种 f[1] = 1; // 1 级:只能走 1 步 f[2] = 2; // 2 级:1+1 或 2 for (int i = 3; i <= N; i++) { f[i] = f[i - 1] + f[i - 2] + f[i - 3]; } printf("%lld\n", f[N]); return 0; }
f[0] = 1 而不是 0?因为递推式 f[3] = f[2] + f[1] + f[0] 中,f[0] 对应"一步走完 3 级"这种方案——它确实是一种合法方案,所以 f[0] 必须计为 1。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
f[0] = 1 | 边界 | 空走法算 1 种 |
f[1] = 1, f[2] = 2 | 边界 | 手工枚举得到 |
f[i] = f[i-1] + f[i-2] + f[i-3] | 递推 | 按"第一步走几级"分三类 |
long long f[70] | 类型 | f[60] 约 7 × 10¹⁵,需 64 位 |
f[0] 写成 0;② 用 int(f[60] 会溢出);③ N ≤ 2 时直接访问 f[N] 是可以的(因为 f[0..2] 都赋了值),但循环要从 3 开始;④ 把"每步 1/2/3 级"误看成"每步必须走 3 级"。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 7 | 题面样例 1 |
10 | 274 | 题面样例 2 |
1 | 1 | 只有 1 级 |
2 | 2 | 1+1 或 2 |
3 | 4 | 1+1+1、1+2、2+1、3 |
60 | 运行验证 | 最大值,验证 long long |
f[60] 约 7 × 10¹⁵,超出 int 范围。一个长度 61 的数组(也可以只用 3 个变量滚动)。
✅ 常数级运算,瞬间完成。本题的价值在于"学会按第一步划分情况"这个递推思路。
// 三项递推(Tribonacci)模板 long long f[70]; f[0] = 1; f[1] = 1; f[2] = 2; for (int i = 3; i <= N; i++) f[i] = f[i-1] + f[i-2] + f[i-3]; // 滚动变量版(空间 O(1)) long long a = 1, b = 1, c = 2; for (int i = 3; i <= N; i++) { long long d = a + b + c; a = b; b = c; c = d; } // 答案 = c // 本题的递推思路是"按第一步分类" // 其实也算 DP:"状态 = 剩余台阶数","决策 = 这一步走几级" // 状态转移:f[i] = Σ f[i - 每步可走的级数] // 如果每步可选 1 ~ k 级,递推式就是 k 项之和 // 如果每步可选任意正整数级,方案数 = 2^(N-1)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 三项递推 | 按第一步分三类 | 走台阶、铺砖、拆数字类计数 |
| 按第一步分类 | 大问题拆小问题 | 所有递推/DP 的切入口 |
| 初始值含义 | 空问题算 1 种 | 避免 f[0] 取错 |
2^(N−1)——因为可以把 N 个台阶之间的 (N−1) 个"缝隙"各自决定"是否在此处停一下"。从这个例子能看出:"可选步长集合"的改变会让递推式随之改变。)