509. Fibonacci Number(斐波那契數列)————附帶詳細解析和代碼

文章目錄

• ​​0 效果​​
• ​​1 題目​​
• ​​2 思路​​

• ​​2.1 動态規劃（打表）​​
• ​​2.2 矩陣快速幂​​
• ​​2.3 通項公式​​

• ​​3 代碼​​

• ​​3.1 打表​​
• ​​3.2 矩陣快速乘​​
• ​​3.3 通項公式​​

0 效果

1 題目

2 思路

2.1 動态規劃（打表）

遞歸寫法為：

int F(int n){
    if(n == 0 || n == 1) return 1;
    else return F(n-1) + F(n-2);
}      

遞歸會涉及到很多重複的計算,如當n==5時，可以得到F(5)= F(4)+F(3),接下來計算F(4)時又會有F(4)= F(3)+F(2),這時不采取措施，F(3)将會被計算兩次。如果n很大，重複計算的次數将難以想象。

實際上由于沒有儲存中間計算的結果，實際複雜度将會高達O(2n),即每次都會計算F(n-1)和F(n-2)這兩個分支，基本上不能承受n較大的情況。

開一個數組dp,用來儲存已經計算過的結果，其中dp[n]記錄F(n)的結果，并用dp[n] = -1來表示F(n) 目前還沒有被計算過。

int dp[MAXN];      

然後就可以在遞歸中判斷dp[n]是否是-1，如果不是-1，說明已經計算過F(n),直接傳回dp[n]就是結果；否則，按照遞歸式進行遞歸。

int F(int n){
    if(n == 0 || n == 1) return  1;
    if(dp[n] != -1) return dp[n];
    else{
        dp[n] = F(n-1) + F(n-2);
        return dp[n];
    }
}      

通過記憶化搜素，把複雜度從O(2n)降到O(n)。

斐波那契數列遞歸圖：

斐波那契數列記憶化搜尋示意圖：

如計算F（45），直接使用遞歸用時9.082809，用記憶化搜尋僅僅0.000001

2.2 矩陣快速幂

以下解析摘自​​官網​​

2.3 通項公式

3 代碼

3.1 打表

class Solution {
public:
    int fib(int n) {
        int dp[31];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n;i++){
            dp[i] = dp[i -1] + dp[i-2];
        }
        return dp[n];
    }
};      

3.2 矩陣快速乘

class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        vector<vector<int>> q{{1, 1}, {1, 0}};
        vector<vector<int>> res = matrix_pow(q, n - 1);
        return res[0][0];
    }

    vector<vector<int>> matrix_pow(vector<vector<int>>& a, int n) {
        vector<vector<int>> ret{{1, 0}, {0, 1}};
        while (n > 0) {
            if (n & 1) {
                ret = matrix_multiply(ret, a);
            }
            n >>= 1;
            a = matrix_multiply(a, a);
        }
        return ret;
    }

    vector<vector<int>> matrix_multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
        vector<vector<int>> c{{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
};      

3.3 通項公式

class Solution {
public:
    int fib(int n) {
        double sqrt5 = sqrt(5);
        double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
        return round(fibN / sqrt5);
    }
};