hello，我又来打卡题解了，前两篇阅读量有20左右，望大家支持！ : )

题目描述

斐波那契数列，又名兔子数列，因规律由兔子繁衍得出（确实奇葩），规律很简单，每个数是他前两个数的和，数列中第一个数默认为1（不然没法做，全是0）第0个为0；下面举个栗子：1,1,2,3,5,8,13,21…；每个数都是前两个的和。
下面看题，今天我主要是给大家写两个动态规划的写法，第二个相比第一个会进行一些空间优化，大家可以有选择性的看一下。

样例

样例输入：

5

样例输出：

5

这个样例怎么看怎么坑，这要不知道的还以为直接输出呢，下面是我提供的一个样例：
样例输入：

10

样例输出：

89

算法1

正常的简单动归

正常的动归做法呢，很简单，由于要取前两个数的和，所以首先需要定义好前两个数的值是1和1，接着我们只需要用循环来求助要求位数的值即可，思路很简单，下面上代码。

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e3; //1e3是科学计数法，就是1乘10的3次方的意思
typedef long long = ll; //防止麻烦，这样做以后ll就是long long类型的意思
ll f[N]; //上面ll就可以这样用，和“long long f[N]”一样
int main() {
    int n;
    cin >> n;//定义并输入要求的位数
    f[0] = f[1] = 1;//定义前两个数的值为1
    for (int i = 2; i <= n; i++) {//注意从2开始循环，0,1定义完了
        f[i] = f[i - 1] + f[i - 2]; //完成规律，每个数是前两个的和
    }
    cout << f[n] << endl; //输出第n位得到的数
    return 0;
}

算法2

这里算法2就进行一下优化，其实完全可以不用数组来做这道题，直接上代码；

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e3;
typedef long long ll;
ll f[N]; //上面说过不在赘述
int main() {
    ll a = 1, b = 1, c = 1; //首先初始化一下数据
    for (int i = 2; i <= n; i++) { //依旧是一样的循环
        c = a + b;
        a = b;
        b = c; //这边和上面的思路一样，但这次要同时更新a,b的值
    }
    cout << c << endl; //最后输出答案
    return 0;
}

一不小心又到底了，不知道今天大家学会了吗，我们下次再见！
各位神犇，蒟蒻求轻虐。