题解 | #斐波那契数列#

题目主要信息:

• 斐波那契数列每项的公式为:$F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+F(n-2)$，从0开始，$F(0)=0F(0)=0$，$F(1)=1F(1)=1$
• 求出斐波那契数列的第n项

具体思路:

既然是数列，我们就把它放入数组中来解决。

• step 1：创建一个长度为$n+1n+1$的vector数组，因为只有$n+1n+1$才能有下标第$nn$项，我们用它记录前$nn$项斐波那契数列。
• step 2：根据公式，初始化第0项和第1项（题目中是第1项和第2项，本质上一样的）。
• step 3：遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到$fib[n]fib[n]$。

相加过程如下图所示：

代码实现:

class Solution {
public:
    int Fibonacci(int n) {
        vector<int> fib(n + 1, 0); //用数组记录斐波那契数列前n项
        fib[1] = 1; //初始化开头两项
        fib[2] = 1;
        for(int i = 3; i <= n; i++) //遍历数组
            fib[i] = fib[i - 1] + fib[i - 2]; //使用公式补齐后面的元素
        return fib[n];
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次数组
• 空间复杂度：$O(n)O(n)$，因为我们要求斐波那契数列第$nn$项，与整个数列没有关系，因此创建数组获取前面的值属于额外空间