题目描述

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

假定从0开始，第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

算法1

(递归) $O(n^2)$

递归的时候，每求一个元素值就要把他之前的所有元素的计算都计算一遍。不过递归通常会引起Stack Overflow。

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n < 1)
        {
            return 0;
        }
        else if(n == 1 || n == 2)
        {
            return 1;
        }
        else
        {
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
};

算法2

(迭代) $O(n)$

先把之前元素得到的计算值保存，当计算下一个元素值时，直接利用已经保存的值，而无需重新计算，提高效率。

迭代的方法效率比较高，时间复杂度是O(n)，空间复杂度是O(1）。

这里我们设计两个变量往后计算，
a表示第n-1项，b表示第n项。
c=a+b。表示第n+1项。

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n < 1)
        {
            return 0;
        }

        int a = 0, b = 1, c = 1;
        while(n--)
        {
            int c  = a+b;
            a = b,b = c;
        }
        return a;

    }
};