数楼梯

题意

楼梯有 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;
}

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 知识

代码

Pythonic 写法

复杂度

总结