P4729 斐波那契数列（基础）

解题思路

第一步：看懂题目。 斐波那契数列是最经典、最基础的递推问题。数列的前两个值都是 1，从第三个数开始，每个数都等于前两个数之和：1, 1, 2, 3, 5, 8, 13, 21, ...。题目要求第 n 个数是多少。

第二步：用数组递推。 用数组 fib 来存数列，fib[1]=1，fib[2]=1，然后用一个循环从 3 开始，依次算出 fib[i]=fib[i-1]+fib[i-2]，最后输出 fib[n] 即可。

第三步：特别提醒——注意数据大小！ 题目括号里特意写了“注意数据大小！！！”的提示。n 的范围是 1<n<90，也就是说 n 最大可以是 89。斐波那契数列增长非常快：第 40 项已经约 1 亿，第 50 项约 1.26×10^10，第 89 项大约是 1.77×10^18。这个数已经接近 long long（64 位有符号整数）能表示的最大值 9.2×10^18，但还在范围内。如果使用 int 类型，第 47 项左右就会溢出变成负数，所以必须用 long long。

第四步：举个例子验证。 第 20 个数是 6765，程序输出正确。另外可以口算前几项感受一下规律：第 1 项 1，第 2 项 1，第 3 项 2，第 4 项 3，第 5 项 5，第 6 项 8，第 7 项 13……每往后一项，数字就增大很多，这正是题目强调要注意数据大小的原因。

第五步：为什么要学这道题？ 这道题虽然简单，但它是很多复杂递推题（比如爬楼梯、兔子繁殖、蜜蜂路线等）的基础。斐波那契数列在自然界中到处可见：向日葵花盘上种子的排列、松果上的鳞片、兔子的繁殖数量，都遵循这个规律。上楼梯问题（一次可以跨一级或两级台阶，问上 n 级台阶有几种跨法）、铺地砖问题（用 1×2 的砖铺 1×n 的路有几种铺法）等，本质上都是斐波那契数列。掌握好“用前两项推出后一项”的递推思想非常重要，学会用数组递推，就能又快又准地求出任意一项。

参考代码

// 斐波那契数列：fib[1]=fib[2]=1，之后每个数等于前两个数之和，求第n项
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long fib[90];  // n最大89，第89项约1.7e18，用long long存
    fib[1] = 1; fib[2] = 1;
    for (int i = 3; i <= n; i++)
        fib[i] = fib[i-1] + fib[i-2];
    cout << fib[n] << endl;
    return 0;
}

复杂度分析

程序从第 3 项递推到第 n 项，只需要一层循环，每步做一次加法，时间复杂度是 O(n)。n 最大为 89，运行时间几乎为零。空间上用一个长度 90 的 long long 数组，空间复杂度 O(n)，非常小。