题解 | #斐波那契数列#

什么是斐波拉契数列
由题意与斐波拉契数列定义:已知f(n)=f(n-1)+f(n-2),f(0)=0,f(1)=1，求f(n)。
题解一:记忆化搜索
图示如下：

根据思路我们可以实现递归代码：

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1) return n;//前两项结果，递归结束条件
        return  Fibonacci(n-1)+Fibonacci(n-2);//递推公式
    }
};

仔细观察上图，可以发现，f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个map存储已经被计算过的值(不采用vector的原因，不确定斐波拉契数列的项数，无法预先申请确定大小的数组)。
具体实现如下：

class Solution {
public:
     map<int,int> map_flag;//记录已经被计算出来的值
    int Fibonacci(int n) {
        if(n<=1) return n;//f(0)=0,f(1)=1,初始状态
        if(map_flag.count(n)){//已经被计算过;采用count的函数可以降低内存与时间；
            return map_flag[n];//第n项的值
        }
        return  map_flag[n]=Fibonacci(n-1)+Fibonacci(n-2);//未被计算过，存入map;
    }
};

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

题解二：动态规划
将记忆化搜索的递归部分修改为迭代。
1、题解一分析出本题f(n)可以拆分出重叠子问题f(n-1)、f(n-2);
2、f(n)=f(n-1)+f(n-2)是动态规划的状态转移方程；
3、f(0)=0,f(1)=1是动态规划的初始状态；
4、dp为一维数组，其中dp[i]的值代表斐波拉契数列第n项的值；

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n),建立一个保存状态的数组;

实现如下:

class Solution {
public:
    int Fibonacci(int n) {
        vector<int> dp(n+1, 0);
        dp[1] = 1;//初始状态
        for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];//状态转移方程
        }
        return dp[n];
    }
};

动态规划优化：状态压缩
我们可以看出：
1、在计算f(3)之后的值时,f(0)再也用不上了，没有必要保存；
2、每一个状态计算直接相关的只有当前值的前2个值；
那么我们可以只用两个值做保存前两个状态：

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

实现如下：

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1)return n;//特别判断斐波拉契数列前两项值
        int l1=0,l2=1;//用来保留前两项的值
        for (int i=2; i<=n; ++i) {
            int temp=l1+l2;
            l1=l2;
            l2=temp;
        }
        return l2;
    }
};

相关题目:
跳台阶
矩形覆盖