题目描述

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

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

这里定义斐波那契数列问题：

定义 a0=0, a1=1, an=a(n−1)+a(n−2),求 an 是多少。

样例

输入整数 n=5 

返回 5

算法1

(递归) 时间复杂度 $O(2^n)$

直接递归，递归计算的节点个数是2^n级别的，存在大量重复计算

C++ 代码

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

算法2

(记忆化搜索) 时间复杂度$O(n)$ 空间复杂度$O(n)$

采取时间换空间的做法，使用一个大的数组计算中间结果，如果某一个状态计算过，直接查表，否则进行递归计算。

C++ 代码

const int N = 40;
int a[N];

class Solution {
public:

    int Fibonacci(int n)
    {
        if (a[n]) return a[n];
        if (n <= 0) return 0;
        if (n == 1) return 1;
        a[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return a[n];
    }
};

算法3

(递推法) 时间复杂度$O(n)$

从下往上计算，首先根据f(0)和f(1)计算f(2),再根据f(1)和f(2)计算f(3),依次类推

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        int res[2] = {0, 1};
        if(n < 2)
            return res[n];

        int a = 0, b = 1;
        int c = 0;
        for(int i = 2; i<=n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

//(递推)变量滚动法：a 表示第 n−1 项，b 表示第 n 项。
//则令 c=a+b 表示第 n+1 项，然后让 a,b 顺次往后移一位。
class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        int c = 0;
        for(int i=2; i<=n;i++)
        {
            c = a + b;
            a = b, b = c;

        }
        return c;
    }
};

算法4

(矩阵运算 + 快速幂) 时间复杂度$O(logn)$

C++ 代码

//求矩阵的幂转化成求数的幂
//递归求幂
//n为奇数
//n为偶数

// 时间复杂度O(logn)


//A2m
class Solution {
public:
    std::pair<int, int> Fib(int n)
    {
        // 返回F{n}和F{n + 1}
        if (n > 0)
        {
            // 基于递归求解.
            auto PF = Fib(n / 2);  
            auto t0 = PF.first;
            auto t1 = PF.second;

            // 奇数情况
            if (n % 2 == 1)        
              return {t0 * t0 + t1 * t1, (2 * t0 + t1) * t1};
            //偶数情况
            else
              return {(2 * t1 - t0) * t0, t0 * t0 + t1 * t1};
        }
        // 基础情形: F0和F1
        return {0, 1};            
    }
    int Fibonacci(int n) {
        return Fib(n).first;
    }
};