BISHI131. 数楼梯
题目描述
给定一段有 n 阶的楼梯，你每一步可以选择上 1 阶或者 2 阶。 求从楼梯底端走到顶端共有多少种不同的走法。 由于答案可能很大，请将结果对 998244353 取模后输出。
输入格式
在一行上输入一个整数 n，表示楼梯的阶数。
输出格式
输出一个整数，表示不同走法的数量对 998244353 取模后的结果。
示例
示例 1
输入：
1
输出：
1
说明： 1 阶楼梯只有「迈 1 阶」一种走法。
示例 2
输入：
4
输出：
5
说明： 5 种走法分别是：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2。
示例 3
输入：
721
输出：
670483856
说明： n 很大时答案会溢出，必须在计算过程中对 998244353 取模。
解题思路
第一步：理解问题本质
设 f(n) 表示「走到第 n 阶的走法数」。考虑最后一步：
- 如果最后一步迈 1 阶，那么之前站在第 n-1 阶，有
f(n-1)种走法； - 如果最后一步迈 2 阶，那么之前站在第 n-2 阶，有
f(n-2)种走法。
最后一步只有这两种可能，所以：
f(n) = f(n-1) + f(n-2)
边界：f(1) = 1（迈 1 阶），f(2) = 2（1+1 或 2）。
第二步：暴力递归
直接按公式递归：
def f(n):
if n <= 2:
return n
return f(n - 1) + f(n - 2)
它会重复计算大量相同的子问题（f(n-2) 被算了很多遍），
复杂度是 O(2^n)，n=721 时完全跑不动。
第三步：递推 + 滚动变量（最优）
把递归改成自底向上的递推，用两个变量滚动保存最近两项：
a, b = 1, 1
for _ in range(n):
a, b = b, (a + b) % MOD
# 循环结束后 a 就是答案
因为取模对加法满足结合律与交换律，每步都取模不改变最终结果， 又能避免大整数越滚越慢。
完整代码实现
本题无可视化步骤：代码里没有可逐帧展示的过程（执行轨迹已经录下来， 但局部变量里找不到推进中的中间状态 —— 比如全篇就是一次正则替换或一次切片）。
import sys
MOD = 998244353
def solve() -> None:
"""斐波那契递推，滚动变量 + 取模"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
a, b = 1, 1 # a = f(1), b = f(2)；滚动到 a = f(n+1)
for _ in range(n):
a, b = b, (a + b) % MOD
sys.stdout.write(str(a % MOD) + "\n")
if __name__ == "__main__":
solve()
示例推演
以 n = 4 为例，初始 a = 1, b = 1：
| 轮次 | 计算前 (a, b) | a + b | 计算后 (a, b) |
|---|---|---|---|
| 1 | (1, 1) | 2 | (1, 2) |
| 2 | (1, 2) | 3 | (2, 3) |
| 3 | (2, 3) | 5 | (3, 5) |
| 4 | (3, 5) | 8 | (5, 8) |
循环结束后 a = 5，即答案为 5，与示例一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) | 大量重复计算 |
| 递推数组 | O(n) | O(n) | 保存整个 dp 数组 |
| 滚动变量 | O(n) | O(1) | 推荐 |
易错点总结
1. 忘记取模
n 到 721 时斐波那契数有约 150 位，虽然 Python 大整数不会溢出， 但数值越滚越大、运算越来越慢；更别说其它语言会直接溢出。 按题目要求在每一步取模。
2. 边界与下标对不上
f(1) = 1、f(2) = 2，不是 f(1) = 1、f(2) = 1。
如果写成标准斐波那契（1,1,2,3,5…），需要确认第 n 项对应的是哪个值。
3. 每步都取模 vs 最后取模
两者结果相同（题目备注也强调了这一点），但每步取模更快、更安全。
扩展思考
- 若允许一次上 1、2、3 阶，递推变成
f(n) = f(n-1)+f(n-2)+f(n-3)。 - 若相邻两步不能相同（比如不能连续迈两次 2 阶），需要给状态加上 「最后一步是几」，变成带状态维度的 DP。