爬楼梯

题目描述

树老师爬楼梯，每次可以走 1 级或 2 级。输入包含若干行，每行一个正整数 $N$ （ $1 \le N \le 30$ ），每行输出走完 $N$ 级的走法数。例如 $N=3$ 时有 $\{1,1,1\},\{1,2\},\{2,1\}$ 共 3 种走法；样例输入为三行 5、8、10，对应输出为 8、34、89。

思路

按最后一步跨 1 级还是 2 级分类，两类互斥且完备，得递推 $f(n)=f(n-1)+f(n-2)$ ，边界 $f(0)=f(1)=1$ ；先预处理出 $1 \sim 30$ 的答案，再对每行询问直接查表输出。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/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 23:30
# update_at: 2026-09-29 23:30

import sys
from functools import cache


@cache
def ways(n: int) -> int:
    """走完 n 级楼梯的走法数：最后一步跨 1 级或 2 级，二者方案互斥且完备。"""
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)


def solve() -> None:
    # 每行一个 N，直接逐个求值；@cache 保证每个 N 只算一次
    out = [str(ways(n)) for n in map(int, sys.stdin.buffer.read().split())]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * 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 05:26
 * update_at: 2026-10-05 05:26
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 35;
ll ways[MAXN]; // ways[i] 表示走完 i 级楼梯的走法数

int main() {
    ways[0] = 1; // 边界：一步不走也算一种方案
    ways[1] = 1; // 边界：只能跨 1 级
    for (int i = 2; i < MAXN; i++) {
        ways[i] = ways[i - 1] + ways[i - 2]; // 按最后一步跨 1 级或 2 级分类
    }

    ll n;
    while (cin >> n) {
        cout << ways[n] << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码