正解如下，防止误导新手。

递推做法，一步步推算就行。

#include<bits/stdc++.h>
using namespace std;
int n;
int f[100010];
int main()
{
    cin >> n;
    f[1] = 1;
    f[0] = 1;
    for(int i = 2; i <= n; i ++) f[i] = f[i - 1] + f[i - 2];
    cout << f[n];
    return 0;
}

下面的都是恶搞！

递归

函数递归。

#include<bits/stdc++.h>
using namespace std;
int n;
int fa(int u)
{
    if(u == 1) return 1;
    if(u == 0) return 1;
    return fa(u - 1) + fa(u - 2);
}
int main()
{
    cin >> n;
    cout << fa(n) << endl;
    return 0;
}

记忆化搜索

开一个f数组进行记忆化搜索。

这个的话主要用于多组数据，现在这个题目用不到，所以说是恶搞。

#include<bits/stdc++.h>
using namespace std;
int n;
int f[100010];
int fa(int u)
{
    if(f[u] != -1) return f[u];
    {
        if(u == 1) 
        {
            f[u] = 1;
            return 1;
        }
        if(u == 0) 
        {
            f[u] = 1;
            return 1;
        }
        int k = fa(u - 1) + fa(u - 2);
        f[u] = k;
        return k;
    }
}
int main()
{
    memset(f, -1, sizeof f);
    cin >> n;
    cout << fa(n) << endl;
    return 0;
}

滚动数组优化递推（dp）

滚动数组记录$i - 2$, $i - 1$和$i$。

记得特判就行了。

#include<bits/stdc++.h>
using namespace std;
int n;
int f[3];
int main()
{
    cin >> n;
    if(n == 0 || n == 1) 
    {
        cout << 1 << endl;
        return 0;
    }
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        f[2] = f[0] + f[1];
        f[0] = f[1];
        f[1] = f[2];
    }
    cout << f[2];
    return 0;
}

尾递归

#include<bits/stdc++.h>
using namespace std;
int n;
int fa(int u, int a, int b)
{
    if(u == 0) return a;
    else return fa(u - 1, b, a + b);
}
int main()
{
    cin >> n;
    cout << fa(n, 1, 1);
    return 0;
}

矩阵乘法/矩阵快速幂

我真的是闲到家了。

step 1：推式子

就是一个Feb数列。

f[n] = f[n - 1] + f[n - 2];

step 2：推矩阵

f[n - 1] = f[n - 1]，矩阵表示：{0， 1}

f[n] = f[n - 1] + f[n - 2]，矩阵表示：{1， 1}

那么矩阵就推出来了。

step 3：写代码

这题不用快速幂也能过。。。

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int a[2][2] = 
{
    {0, 1},
    {1, 1}
};
int n;
int f[2] = {1, 1};
void mo(int f[])
{
    int ans[2] = {0};
    for(int i = 0; i < 2; i ++)
    {
        for(int j = 0; j < 2; j ++)
        {
            ans[i] += f[j] * a[i][j];
        }
    }
    for(int i = 0; i < 2; i ++) f[i] = ans[i];
}
int main()
{
    cin >> n;
    for(int i = 1; i < n; i ++) mo(f);
    cout << f[1];
}