【例67.1】 爬楼梯

解题思路

f[k]表示走到第k阶的方案。最后一步来自k-1或k-2，故f[k]=f[k-1]+f[k-2]，f[0]=1、f[1]=1。预处理到30后读多组查询。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

输入没有组数，读到EOF；每行一个结果。

复杂度

预处理O(30)，每查询O(1)，空间O(30)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long f[31] = {1, 1};
    for (int i = 2; i <= 30; i++)
        f[i] = f[i - 1] + f[i - 2];
    int n;
    while (cin >> n)
        cout << f[n] << "\n";
    return 0;
}