题目描述

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

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

数据范围

0≤n≤39

样例

输入整数 n=5 

返回 5

解法1

暴力递归【自顶向下】

涉及到递归问题画一个递归树，有助于分析算法的复杂度以及寻找算法低效的原因。

递归算法的时间复杂度=子问题个数×解决一个子问题需要的时间
子问题个数：O(2^n)
解决一个子问题的时间：Fibonacci(n-1)+Fibonacci(n-2) ， 是O(1)
所以时间复杂度是：O(2^n)，爆炸
观察递归树，发现算法低效的原因：存在大量重复计算，即重叠子问题。(重叠子问题是动态规划问题的一个性质)

时间复杂度

$O(2^n)$

参考文献

labuladong

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(1)
所以时间复杂度：$O(n)$

时间复杂度

$O(n)$

参考文献

labuladong

C++ 代码

int memo[42];
class Solution {
public:
    //自带的函数（没办法删，但是可以调用我自己的函数）
    int Fibonacci(int n) {
        memo[0]=0,memo[1]=1;
        my_Fb(n);
    }

    //我写的函数（可以作为最终return结果的函数）
    int my_Fb(int n)
    {
        if(n==0 || memo[n])  return memo[n];  //在memo里，直接return

        memo[n] = my_Fb(n-1) + my_Fb(n-2);  //不在memo里，先算好存里面，再return
        return memo[n];
    }
};

解法3

递推(动态规划思想) 【自底向上】

递推图：

时间复杂度

$O(n)$

参考文献

labuladong

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        int a[42];
        a[0]=0,a[1]=1;
        for(int i=2;i<=n;i++)
        {
            a[i]=a[i-1]+a[i-2];  //递推核心式子，即状态转移方程
        }
        return a[n];
    }

};

算法3的优化：

根据递推代码，发现当前状态只和前两个状态有关，只需要存储前两个状态即可，可以将时间复杂度降为O(1)

C++代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n<2)  return n;

        int pre_a = 0 , pre_b = 1;
        int sum;
        for(int i=2;i<=n;i++)
        {
            sum = pre_a + pre_b;  //只记录两个变量及其和，并且时刻更新这两个变量
            pre_a = pre_b;
            pre_b = sum;
        }
        return sum;
    }
};