P1255 数楼梯

题目描述

楼梯有 \(N\) 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例 #1

输入 #1

4

输出 #1

5

说明/提示

• 对于 \(60\%\) 的数据，\(N \leq 50\)；
• 对于 \(100\%\) 的数据，\(1 \le N \leq 5000\)。

Tip

B站讲解

---

📌 题目分析

👉 本质： 从 1 到 N，每次可以走：

1步 或 2步

问总方案数

👉 类型： 动态规划（斐波那契）+ 高精度

---

🧠 解题思路

1️⃣ 核心建模

设：

dp[i] = 到第 i 阶的方法数

2️⃣ 状态转移（核心）

到第 i 阶，可以从：

• 第 i-1 阶走 1 步
• 第 i-2 阶走 2 步

所以：

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

👉 这就是：

斐波那契数列！

3️⃣ 初始条件

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

4️⃣ 关键难点 ❗（本题核心）

N ≤ 5000

👉 dp[5000] 非常巨大！

普通类型：

• ❌ int 不行
• ❌ long long 不行

👉 必须用：

高精度（大整数）

5️⃣ 高精度实现方式

👉 用字符串存储大数

核心操作：

字符串加法

6️⃣ 时间复杂度

O(n × 位数)

👉 可以通过 ✅

---

💻 C++代码（高精度 + DP）

#include <bits/stdc++.h>
using namespace std;

// 高精度加法（字符串）
string add(string a, string b) {
    string res = "";
    int carry = 0;

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int n = max(a.size(), b.size());

    for (int i = 0; i < n; i++) {
        int x = (i < a.size() ? a[i] - '0' : 0);
        int y = (i < b.size() ? b[i] - '0' : 0);

        int sum = x + y + carry;
        res += (sum % 10 + '0');
        carry = sum / 10;
    }

    if (carry) res += (carry + '0');

    reverse(res.begin(), res.end());
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n == 1) {
        cout << 1;
        return 0;
    }

    vector<string> dp(n + 1);
    dp[1] = "1";
    dp[2] = "2";

    for (int i = 3; i <= n; i++) {
        dp[i] = add(dp[i - 1], dp[i - 2]);
    }

    cout << dp[n];

    return 0;
}

---

⚠️ 易错点

❌ 1. 用 long long

dp[100] 就已经爆了

❌ 2. 字符串没反转

必须 reverse 才能从低位加

❌ 3. 忘记处理进位

carry

❌ 4. n=1 特判

🚀 一句话总结

斐波那契 + 高精度加法

🔥 关键提升（你现在非常关键阶段）

你已经掌握：

• ✅ 排序（快排、计数）
• ✅ 分治（QuickSelect）
• ✅ 基础 DP（网格）
• ✅ 斐波那契 DP

👉 本题让你掌握：

高精度 DP（非常重要）

---