【例86.1】 上台阶

解题思路

f[i]表示到第i阶的方案，最后一步可能为1、2、3阶，所以f[i]=f[i-1]+f[i-2]+f[i-3]，f0=1，负下标视0。n≤70时结果可超64位，使用字符串大整数预处理。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

0是结束标志不输出；不能误用只走1或2阶的斐波那契。

复杂度

最大D位，预处理O(70D)，空间O(70D)。

参考代码（C++11）

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

string addBig(string a, string b) {
    string s;
    int i = a.size() - 1, j = b.size() - 1, c = 0;
    while (i >= 0 || j >= 0 || c) {
        int v = c;
        if (i >= 0)
            v += a[i--] - '0';
        if (j >= 0)
            v += b[j--] - '0';
        s += char('0' + v % 10);
        c = v / 10;
    }
    while (s.size() > 1 && s.back() == '0')
        s.pop_back();
    reverse(s.begin(), s.end());
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> f(71, "0");
    f[0] = "1";
    for (int i = 1; i <= 70; i++)
        for (int d = 1; d <= 3; d++)
            if (i >= d)
                f[i] = addBig(f[i], f[i - d]);
    int n;
    while (cin >> n && n)
        cout << f[n] << "\n";
    return 0;
}