GESP 题解库 / 6 级题解 / [GESP样题 六级] 下楼梯 · 第 23 / 27 题
GESP样题 六级 · P10250 · 简单

下楼梯

每步可走 1/2/3 个台阶,N 个台阶共有多少种走法。

📊
N ≤ 60
台阶数
🔢
long long
方案数
⚡
O(N)
时间复杂度
🎯
三项递推(类斐波那契)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

一共有 N 个台阶,每步可以走 1 个、2 个或 3 个台阶。求走完 N 个台阶共有多少种不同的方案。

💡
人话翻译:最经典的递推入门题。考虑最后一步:它可能是走 1 步、2 步或 3 步。
所以 f[N] = f[N−1] + f[N−2] + f[N−3]。
也就是把"从 0 级走到 N 级"拆成"先走到 N−1 再走 1 步"、"先走到 N−2 再走 2 步"、"先走到 N−3 再走 3 步"三种情况相加。这就是"三项斐波那契"(Tribonacci)。

🔍 关键词提取

递推最后一步划分三项斐波那契边界处理

已知条件

项目说明
输入一个整数 N
输出走法的总数
数据范围1 ≤ N ≤ 60
每步选择1、2 或 3 个台阶
方案区分按"每步走多少"的序列区分

需要解决的问题

02
思维导图
整理解题思路的全貌
🪜 f[N] = f[N−1] + f[N−2] + f[N−3]
🧠 划分依据
看第一步走几级
走 1 级 → 剩下 N−1 级
走 2 级 → 剩下 N−2 级
走 3 级 → 剩下 N−3 级
📐 初始值
f[0] = 1(不走也算一种)
f[1] = 1
f[2] = 2
从 f[3] 起用递推
🔢 数值增长
1, 1, 2, 4, 7, 13, 24, 44, …
增长约 1.839 倍
N = 60 时约 7 × 10¹⁵
正好在 long long 内
⚠️ 易错点
f[0] 写成 0 导致后面全错
用 int(N = 60 时溢出)
下标越界(N ≤ 2 时不能直接递推)
把"台阶数"和"方案数"搞混
03
样例手算推导
样例与递推表的验证

🧮 样例 1:N = 4,答案 7

先按递推算,再手工枚举核对。

1
初始值

f[0] = 1(一级都不走,也只有这一种"走法")

f[1] = 1(只能一次走 1 级)

f[2] = 2(1+1 或 一次走 2 级)

f = [1, 1, 2, …]

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

📊 手工枚举 N = 4 的所有方案

序号走法(每步台阶数)步数
11 + 1 + 1 + 14
21 + 1 + 23
31 + 2 + 13
42 + 1 + 13
51 + 32
63 + 12
72 + 22

共 7 种 ✓ 与递推一致

🔑
注意"步数不同也算不同方案":1+3 和 3+1 是两种方案,因为它们每一步的走法序列不同。这与"只问用了几步"的问题完全不同——读题时要看清"方案"的定义。

🧮 样例 2:N = 10,答案 274

继续把递推表算下去。

N012345678910
f[N]1124713244481149274

f[10] = 274 ✓ 与样例一致

1
验证几个值

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 ✓

全部吻合

⚠️
关于数据范围 N ≤ 60:这题如果用 O(2^N) 的搜索枚举所有方案,N = 60 时完全不可行;但递推只要 O(N) 次加法。
而且 f[60] 约为 7 × 10¹⁵,恰好超出 int(约 2.1 × 10⁹)但仍在 long long 内——这也是题目把 N 限制在 60 的原因之一。
04
解法对比
递推 O(N) vs 搜索枚举

⚔️ 解法对比

🟢 线性递推(推荐) 推荐

f[i] = f[i−1] + f[i−2] + f[i−3]

  • 时间 O(N)
  • N = 60 时 60 次加法
  • 代码 10 行
  • 空间可优化到 O(1)
💡
递推的本质:把"大问题"按第一步的走法拆成三个"小问题"。这种"按第一步/最后一步分类"是递推与 DP 最常用的切入点。

🟠 搜索枚举所有走法

递归生成所有"每步走几级"的序列

  • 方案数约 1.839^N
  • N = 40 时已约 10¹⁰ 种
  • N = 60 完全不可行
  • 只能处理 N ≤ 15 左右
⚠️
对比量级:搜索要枚举"所有方案",而递推只算"方案的个数"——这正是 DP 的核心价值:用状态合并掉大量重复的子结构。

📈 性能对比

方案复杂度(N = 60)可行性
线性递推60 次加法✅ 瞬间
搜索枚举约 7 × 10¹⁵ 种❌ 不可行
05
算法流程图
从 f[0] 递推到 f[N]
开始读入 Nf[0] = 1;f[1] = 1;f[2] = 2(注意 N 较小时要特判)i 从 3 遍历到 Nf[i] = f[i − 1] + f[i − 2] + f[i − 3]i 是否已经到 N?输出 f[N]i 加 1 递推下一个
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🪜 下楼梯方案数

输入台阶数 N,程序会递推给出方案数并展示每一步的值。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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。
这体现了"初始值要结合实际含义来定":空问题的方案数是 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 级"。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
47题面样例 1
10274题面样例 2
11只有 1 级
221+1 或 2
341+1+1、1+2、2+1、3
60运行验证最大值,验证 long long
✅
自查清单:① f[0] = 1 吗?② 用 long long 吗?③ 递推式三项都对吗?

🚨 易错点清单

⚠️
f[0] 写成 0:会导致 f[3] 少 1(应为 4),后续全错。
⚠️
用 int:f[60] 约 7 × 10¹⁵,超出 int 范围。
⚠️
循环起点错:应从 i = 3 开始(f[0..2] 已手工赋值)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N)
空间复杂度
O(N)
N 最大
60
运算量
60 次加法

时间怎么算的?

空间都用在哪?

一个长度 61 的数组(也可以只用 3 个变量滚动)。

✅ 常数级运算,瞬间完成。本题的价值在于"学会按第一步划分情况"这个递推思路。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 三项递推(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] 取错
🌟
思考题:如果题目改成"每步可以走 1 到 N 级中的任意级"(即一次最多走多少不限),方案数是多少?(提示:那答案就是 2^(N−1)——因为可以把 N 个台阶之间的 (N−1) 个"缝隙"各自决定"是否在此处停一下"。从这个例子能看出:"可选步长集合"的改变会让递推式随之改变。)