数楼梯

题意

楼梯有 n 阶，每次可以走 1 阶或 2 阶。问走到第 n 阶有多少种不同走法。

思路

设 dp[i] 表示走到第 i 阶的方案数。

最后一步只有两种可能：

从第 i-1 阶走 1 阶；
从第 i-2 阶走 2 阶。

所以：

text

1dp[i] = dp[i-1] + dp[i-2]

初始：

text

1
2dp[1] = 1
dp[2] = 2

小 DP 表

i	1	2	3	4	5
dp[i]	1	2	3	5	8

样例 n=4，答案为 5。

Python 知识

Python 的 int 支持大整数，适合这类高精度递推题。
只需要保留前两项 previous 和 current，不用保存整个 DP 数组。
previous, current = current, previous + current 是 Python 常见的状态滚动写法。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10n = int(input())

if n <= 2:
    print(n)
else:
    previous = 1
    current = 2
    for _ in range(3, n + 1):
        previous, current = current, previous + current
    print(current)

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
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n;
char a[2000], b[2000], c[2000];

void add(char *res, char *x, char *y) {
    int lenx = strlen(x), leny = strlen(y);
    int carry = 0, k = 0, i = lenx - 1, j = leny - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += x[i--] - '0';
        if (j >= 0) sum += y[j--] - '0';
        carry = sum / 10;
        res[k++] = sum % 10 + '0';
    }
    res[k] = '\0';
    reverse(res, res + k);
}

int main() {
    cin >> n;
    if (n == 1) { cout << 1 << endl; return 0; }
    if (n == 2) { cout << 2 << endl; return 0; }
    strcpy(a, "1");
    strcpy(b, "2");
    for (int i = 3; i <= n; i++) {
        add(c, a, b);
        strcpy(a, b);
        strcpy(b, c);
    }
    cout << b << endl;
    return 0;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * 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-08-14 15:18
 * update_at: 2026-08-14 15:18
 */
/* P1255 数楼梯：递推 f(n) = f(n-1) + f(n-2)，答案超出 64 位整数，用字符串模拟高精度加法。 */

#include <iostream>
#include <string>
#include <algorithm>

// 高精度加法：把两个用十进制字符串表示的大数相加
std::string add_big(const std::string& x, const std::string& y) {
    std::string result;
    int carry = 0;
    int i = (int)x.size() - 1;  // 从最低位开始
    int j = (int)y.size() - 1;

    // 两个数都没加完，或者还有进位时继续
    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) {
            sum += x[i] - '0';
            i -= 1;
        }
        if (j >= 0) {
            sum += y[j] - '0';
            j -= 1;
        }
        carry = sum / 10;
        result.push_back(char(sum % 10 + '0'));  // 先得到低位，最后整体反转
    }

    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n;
    std::cin >> n;

    std::string before = "1";   // 走到第 1 阶：1 种走法
    std::string current = "2";  // 走到第 2 阶：2 种走法
    if (n == 1) {
        std::cout << before << '\n';
        return 0;
    }

    // 只滚动保留前两项，避免保存整个 dp 数组
    for (int step = 3; step <= n; step += 1) {
        std::string next = add_big(before, current);
        before = current;
        current = next;
    }

    std::cout << current << '\n';
    return 0;
}

Pythonic 写法

滚动斐波那契：

python

1
2
3
4
5
6
7
8n = int(input())
if n <= 2:
    print(n)
else:
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    print(b)

复杂度

时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

总结

这题是斐波那契递推。Python 的大整数让它比 C++ 高精度写法简单很多。

目录

题意

思路

小 DP 表

Python 知识

代码

Guide 风格代码

Pythonic 写法

复杂度

总结