按最后一步跨 1/2/3 阶分类得三阶线性递推，先打表再回答多组询问。
OJ: roj
题目 ID: 1190
难度:入门
标签:入门递推动态规划记忆化python
创建: 2026-09-29 22:51
更新: 2026-10-05 04:48
题目描述
楼梯有 n（0 < n < 71）阶台阶，一步可上 1/2/3 阶，求走法总数。多行输入，每行一个 n，以 0 结束，每行输出对应方案数。样例：输入 1 2 3 4 0 输出 1 2 4 7。
思路
按最后一步跨 1/2/3 阶分三类得
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:51
# update_at: 2026-09-29 22:51
import sys
from functools import cache
from itertools import takewhile
@cache
def ways(n: int) -> int:
"""上到第 n 阶的走法数：把 n 拆成 1/2/3 之和的有序方案数。
最后一步只能跨 1、2 或 3 阶，所以 ways(n) 等于前三项之和；
n = 0 的空走法记 1 种，正是递推的种子，n = 1 也恰好是 1。
"""
return ways(n - 1) + ways(n - 2) + ways(n - 3) if n > 2 else max(n, 1)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
queries = list(takewhile(int, data)) # 逐行读询问，遇到 0 结束
# @cache 让每个下标只被真正算一次，全部询问共享同一份递推结果
print('\n'.join(map(str, map(ways, queries))))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 04:48
* update_at: 2026-10-05 04:48
*/
#include <iostream>
using namespace std;
typedef long long ll;
// 打表：w[0..70]，w[i] 表示上 i 阶的走法数
// 递推：w(n) = w(n-1) + w(n-2) + w(n-3)，边界 w(0)=1, w(1)=1, w(2)=2
const int MAXN = 71; // 题目要求 0 < n < 71
ll w[MAXN];
int main() {
// 初始化边界
w[0] = 1; // 空走法
w[1] = 1;
w[2] = 2;
// 从小到大递推填表，每格只依赖前三个
for (int i = 3; i < MAXN; i++) {
w[i] = w[i - 1] + w[i - 2] + w[i - 3];
}
// 多组询问，每行一个 n，遇到 0 结束
int n;
while (cin >> n && n != 0) {
cout << w[n] << "\n";
}
return 0;
}