题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从 0 开始，第 0 项为 0。

数据范围

0≤n≤39

样例

输入整数 n=5 
返回 5

方法一：递推 O(n)

我们可以只用常数个变量来进行计算，具体思路如下：

初始化 a=0 和 b=1 ，如果 n=0 则直接返回 a=0 。

如果 n>0 则计算 c=a+b ，然后将 a 和 b 往后移一位即 a=b,b=c 。

来看个例子加深一下印象，假设传入参数 n 为 4 ：

第一步： 初始化变量 a=0,b=1 。

第二步： 开始循环，计算 c=a+b=1 ，a 更新为 b ，b 更新为 c ，并且 n 要减 1 。

第三步 ~ 第五步： 和第二步一样，类似于是一个滚动数组，一直往后面移动。

第六步： 直到 n 为 0 ，返回 a 就是最终的答案。

class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n--)
        {
            int c = a + b;
            a = b, b = c;
        }
        return a;
    }
};

欢迎大家在评论区交流~