数楼梯

GitHub跳转原题关系图返回列表

用斐波那契式递推统计到达第 n 阶的走法，利用 Python 大整数直接处理 n 到 5000 的答案。

OJ: luogu

题目 ID: P1255

难度:入门

标签:动态规划递推python

创建: 2026-07-15 21:50

更新: 2026-08-14 16:33

后置题目
roj 3562传球游戏B 直接复用 A 教的「最后一步只有两种来源就相加」计数模板：把 dp[i]=dp[i-1]+dp[i-2] 换成环上左右邻居两个前驱相加，仅额外套一层 (j±1)%n 绕回，难度落在 A 之上两档。acwing 1015摘花生B 把 A 教的「按最后一步分类、从前驱方案递推」这一步从一维爬楼梯推广到二维网格（每格只可能从上方或左方走来，取更优前驱加 a[i][j]），并叠加网格边界与多组数据处理。luogu P2840纸币问题 2B 的 dp[j] 直接沿用 A 教的「方案数记在 dp[状态]、按最后一步分类求和」这一状态设计与转移：A 的最后一步只有走 1 阶或 2 阶两种，B 把可选前驱扩成所有面额并允许无限次重复，得 dp[j]=Σdp[j-a_i]，再叠加先金额后纸币的循环顺序与取模完成排列计数。luogu P1002[NOIP 2002 普及组] 过河卒B 的过河卒直接复用 A 教的按最后一步累加：A 用 dp[i]=dp[i-1]+dp[i-2] 数走到第 i 阶的方案，B 的 main.cpp 同样写 dp[i][j]+=dp[i-1][j]; dp[i][j]+=dp[i][j-1] 且 dp[0][0]=1，只是把一维台阶换成二维网格并额外把马控制格强制置 0。

目录

  1. 题意
  2. 思路
    1. Python 知识
    2. 代码
    3. Guide 风格代码
    4. Pythonic 写法
    5. 复杂度
    6. 总结

    题意

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

    思路

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

    最后一步只有两种可能：

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

    所以：

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

    初始：

    text
    dp[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
    n = 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
    /**
 * 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
    /**
 * 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
    n = 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(n)，空间复杂度为 O(1)O(1)。

    总结

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