斐波拉契數(shù)列的演變過程是什么

本篇內(nèi)容介紹了“斐波拉契數(shù)列的演變過程是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

1：暴力遞歸

經(jīng)常我們面對(duì)一個(gè)問題，即使我們明確知道了它是一個(gè)“無后效性”問題，它可以通過「動(dòng)態(tài)規(guī)劃」來解決。我們還是覺得難以入手。

這時(shí)候我的建議是，先寫一個(gè)「暴力遞歸」的版本。

還是以剛剛說到的 LeetCode 62. Unique Paths 舉例：

class Solution {
    public int uniquePaths(int m, int n) {
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

當(dāng)我還不知道如何使用「動(dòng)態(tài)規(guī)劃」求解時(shí)，我會(huì)設(shè)計(jì)一個(gè)遞歸函數(shù) recursive() 。

函數(shù)傳入矩陣信息和機(jī)器人當(dāng)前所在的位置，返回在這個(gè)矩陣?yán)铮瑥臋C(jī)器人所在的位置出發(fā)，到達(dá)右下角有多少條路徑。

有了這個(gè)遞歸函數(shù)之后，那問題其實(shí)就是求解 recursive(m, n, 0, 0)：求解從 (0,0) 到右下角的路徑數(shù)量。

接下來，實(shí)現(xiàn)這個(gè)函數(shù)：

1. Base case: 由于題目明確了機(jī)器人只能往下或者往右兩個(gè)方向走，所以可以定下來遞歸方法的 base case 是當(dāng)已經(jīng)處于矩陣的最后一行或者最后一列，即只一條路可以走。

2. 其余情況：機(jī)器人既可以往右走也可以往下走，所以對(duì)于某一個(gè)位置來說，到達(dá)右下角的路徑數(shù)量等于它右邊位置到達(dá)右下角的路徑數(shù)量 + 它下方位置到達(dá)右下角的路徑數(shù)量。即 recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1)，這兩個(gè)位置都可以通過遞歸函數(shù)進(jìn)行求解。

其實(shí)到這里，我們已經(jīng)求解了這個(gè)問題了。

但這種做法還有個(gè)嚴(yán)重的性能問題。

2：記憶化搜索

如果將我們上述的代碼提交到 LeetCode，會(huì)得到 timeout 的結(jié)果。

可見「暴力遞歸」的解決方案“很慢”。

我們知道所有遞歸函數(shù)的本質(zhì)都是“壓?！焙汀皬棗！薄?/p>

既然這個(gè)過程很慢，我們可以通過將遞歸版本暴力解法的改為非遞歸的暴力解法，來解決 timeout 的問題嗎？

答案是不行，因?yàn)閷?dǎo)致 timeout 的原因不在于使用“遞歸”手段所帶來的成本。

而在于在計(jì)算過程，我們進(jìn)行了多次的重復(fù)計(jì)算。

我們嘗試展開遞歸過程第幾步來看看：

不難發(fā)現(xiàn)，在遞歸展開過程會(huì)遇到很多的重復(fù)計(jì)算。

隨著我們整個(gè)遞歸過程的展開，重復(fù)計(jì)算的次數(shù)會(huì)呈倍數(shù)增長(zhǎng)。

這才是「暴力遞歸」解決方案“慢”的原因。

既然是重復(fù)計(jì)算導(dǎo)致的 timeout，我們自然會(huì)想到將計(jì)算結(jié)果進(jìn)行“緩存”的方案：

class Solution {
    private int[][] cache;

    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            if (cache[i + 1][j] == -1) {
                cache[i + 1][j] = recursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {
                cache[i][j + 1] = recursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }
}

對(duì)「暴力遞歸」過程中的中間結(jié)果進(jìn)行緩存，確保相同的情況只會(huì)被計(jì)算一次的做法，稱為「記憶化搜索」。

做了這樣的改進(jìn)之后，提交 LeetCode 已經(jīng)能 AC 并得到一個(gè)不錯(cuò)的評(píng)級(jí)了。

我們?cè)偌?xì)想一下就會(huì)發(fā)現(xiàn)，其實(shí)整個(gè)求解過程，對(duì)于每個(gè)情況（每個(gè)點(diǎn)）的訪問次數(shù)并沒有發(fā)生改變。

只是從「以前的每次訪問都進(jìn)行求解」改進(jìn)為「只有第一次訪問才真正求解」。

事實(shí)上，我們通過查看 recursive() 方法就可以發(fā)現(xiàn)：

當(dāng)我們求解某一個(gè)點(diǎn) (i, j) 的答案時(shí)，其實(shí)是依賴于 (i, j + 1) 和 (i + 1, j) 。

也就是每求解一個(gè)點(diǎn)的答案，都需要訪問兩個(gè)點(diǎn)的結(jié)果。

這種情況是由于我們采用的是“自頂向下”的解決思路所導(dǎo)致的。

我們無法直觀確定哪個(gè)點(diǎn)的結(jié)果會(huì)在什么時(shí)候被訪問，被訪問多少次。

所以我們不得不使用一個(gè)與矩陣相同大小的數(shù)組，將所有中間結(jié)果“緩存”起來。

換句話說，「記憶化搜索」解決的是重復(fù)計(jì)算的問題，并沒有解決結(jié)果訪問時(shí)機(jī)和訪問次數(shù)的不確定問題。

2.1：次優(yōu)解版本的「記憶化搜索」

關(guān)于「記憶化搜索」最后再說一下。

網(wǎng)上有不少博客和資料在編寫「記憶化搜索」解決方案時(shí)，會(huì)編寫類似如下的代碼：

class Solution {
    private int[][] cache;

    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            cache[i][j] = recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }
}

可以和我上面提供的解決方案作對(duì)比。主要區(qū)別在于 if (cache[i][j] == -1) 的判斷里面。

在我提供解決方案中，會(huì)在計(jì)算 cache[i][j] 時(shí)，嘗試從“緩存”中讀取 cache[i + 1][j] 和 cache[i][j + 1]，確保每次調(diào)用 recursive() 都是必須的，不重復(fù)的。

網(wǎng)上大多數(shù)的解決方案只會(huì)在外層讀取“緩存”，在真正計(jì)算 cache[i][j] 的時(shí)候并不采取先檢查再調(diào)用的方式，直接調(diào)用 recursive() 計(jì)算子問題 。

雖然兩者相比與直接的「暴力遞歸」都大大減少了計(jì)算次數(shù)（recursive() 的訪問次數(shù)），但后者的計(jì)算次數(shù)顯然要比前者高上不少。

你可能會(huì)覺得反正都是“自頂向下”，兩者應(yīng)該沒有區(qū)別吧？

為此我提供了以下實(shí)驗(yàn)代碼來比較它們對(duì) recursive() 的調(diào)用次數(shù)：

class Solution {
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.uniquePaths(15, 15);
    }
    
    private int[][] cache;
    private long count; // 統(tǒng)計(jì) 遞歸函數(shù) 的調(diào)用次數(shù)    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        // int result = recursive(m, n, 0, 0); // count = 80233199        // int result = cacheRecursive(m, n, 0, 0); // count = 393        int result = fullCacheRecursive(m, n, 0, 0); // count = 224        System.out.println(count);
        return result;
    }

    // 完全緩存     private int fullCacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            if (cache[i + 1][j] == -1) {
                cache[i + 1][j] = fullCacheRecursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {
                cache[i][j + 1] = fullCacheRecursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }

    // 只有外層緩存    private int cacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            cache[i][j] = cacheRecursive(m, n, i + 1, j) + cacheRecursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }

    // 不使用緩存    private int recursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

因?yàn)槲覀兪褂?cache 數(shù)組的目的是減少 recursive() 函數(shù)的調(diào)用。

只有確保在每次調(diào)用 recursive() 之前先去 cache 數(shù)組檢查，我們才可以將對(duì) recursive() 函數(shù)的調(diào)用次數(shù)減到最少。

在數(shù)據(jù)為 15 的樣本下，這是 O(393n) 和 O(224n) 的區(qū)別，但對(duì)于一些卡常數(shù)特別嚴(yán)重的 OJ，尤其重要。

所以我建議你在「記憶化搜索」的解決方案時(shí)，采取與我一樣的策略：

確保在每次訪問遞歸函數(shù)時(shí)先去“緩存”檢查。盡管這有點(diǎn)“不美觀”，但它能發(fā)揮「記憶化搜索」的最大作用。

3：從「自頂向下」到「自底向上」

你可能會(huì)想，為什么我們需要改進(jìn)「記憶化搜索」，為什么需要明確中間結(jié)果的訪問時(shí)機(jī)和訪問次數(shù)？

因?yàn)橐坏┪覀兡苊鞔_中間結(jié)果的訪問時(shí)機(jī)和訪問次數(shù)，將為我們的算法帶來巨大的提升空間。

前面說到，因?yàn)槲覀儫o法確定中間結(jié)果的訪問時(shí)機(jī)和訪問次數(shù)，所以我們不得不“緩存”全部中間結(jié)果。

但如果我們能明確中間結(jié)果的訪問時(shí)機(jī)和訪問次數(shù)，至少我們可以大大降低算法的空間復(fù)雜度。

這就涉及解決思路的轉(zhuǎn)換：從「自頂向下」到「自底向上」 。

如何實(shí)現(xiàn)從「自頂向下」到「自底向上」的轉(zhuǎn)變，還是通過具體的例子來理解。

這是 LeetCode 509. Fibonacci Number，著名的“斐波那契數(shù)列”問題。

如果不了解什么是“斐波那契數(shù)列”，可以查看對(duì)應(yīng)的 維基百科。

由于斐波那契公式為：

天然適合使用遞歸：

public class Solution {
    private int[] cache;
    public int fib(int n) {
        cache = new int[n + 1];
        return recursive(n);
    }

    private int recursive(int n) {
        if (n <= 1) return n;
        if (n == 2) return 1;
        if (cache[n] == 0) {
            if (cache[n - 1] == 0) {
                cache[n - 1] = recursive(n - 1);
            }
            if (cache[n - 2] == 0) {
                cache[n - 2] = recursive(n - 2);
            } 
            cache[n] = cache[n - 1] + cache[n - 2];
        }
        return cache[n];
    }
}

但這仍然會(huì)有我們之前所說的問題，這些問題都是因?yàn)橹苯舆f歸是“自頂向下”所導(dǎo)致的。

這樣的解法的時(shí)空復(fù)雜度為 O(n) ：每個(gè)值計(jì)算一次，使用了長(zhǎng)度為 n + 1 的數(shù)組。

通過觀察斐波那契公式，我們可以發(fā)現(xiàn)要計(jì)算某個(gè) n ，只需要知道 n - 1 的解和 n - 2 的解。

同時(shí) n = 1 和 n = 2 的解又是已知的（base case）。

所以我們大可以從 n = 3 出發(fā)，逐步往后迭代得出 n 的解。

由于計(jì)算某個(gè)值的解，只依賴該值的前一位的解和前兩位的解，所以我們只需要使用幾個(gè)變量緩存最近的中間結(jié)果即可：

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        if (n == 2) return 1;
        
        int prev1 = 1, prev2 = 1;
        int cur = prev1 + prev2;
        for (int i = 3; i <= n; i++) {
            cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return cur;
    }
}

這樣我們就把原本空間復(fù)雜度為 O(N) 的算法降低為 O(1) ：只是用了幾個(gè)有限的變量。

但不是所有的「動(dòng)態(tài)規(guī)劃」都像“斐波那契數(shù)列”那么簡(jiǎn)單就能實(shí)現(xiàn)從“自頂向下”到“自底向上”的轉(zhuǎn)變。

當(dāng)然也不是毫無規(guī)律可循，尤其是我們已經(jīng)寫出了「暴力遞歸」的解決方案。

讓我們?cè)俅位氐?nbsp;LeetCode 62. Unique Paths 當(dāng)中：

class Solution {
    public int uniquePaths(int m, int n) {
        // 由于我們的「暴力遞歸」函數(shù)，真正的可變參數(shù)就是 i 和 j（ 變化范圍分別是 [0,m-1] 和 [0, n-1] ）        // 所以建議一個(gè)二維的 dp 數(shù)組進(jìn)行結(jié)果存儲(chǔ)（相當(dāng)于建一個(gè)表格）        int[][] dp = new int[m][n];
        
        // 根據(jù)「暴力遞歸」函數(shù)中的 base case        // 我們可以直接得出 dp 中最后一行和最后一列的值（將表格的最后一行和最后一列填上）        for (int i = 0; i < n; i++) dp[m - 1][i] = 1        for (int i = 0; i < m; i++) dp[i][n - 1] = 1;
        
        // 根據(jù)「暴力遞歸」函數(shù)中對(duì)其他情況的處理邏輯（依賴關(guān)系）編寫循環(huán)        //（根據(jù)表格的最后一行和最后一列的值，得出表格的其他格子的值）        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        
        // 最終我們要的是 dp[0][0]（表格中左上角的位置，也就起點(diǎn)的值）        return dp[0][0];
        
        // 原「暴力遞歸」調(diào)用        // return recursive(m, n, 0, 0);    }

    private int recursive(int m, int n, int i, int j) {
        // base case        if (i == m - 1 || j == n - 1) return 1;
        // 其余情況        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

不難發(fā)現(xiàn)，我們甚至可以直接根據(jù)「暴力遞歸」來寫出「動(dòng)態(tài)規(guī)劃」，而不需要關(guān)心原問題是什么。

簡(jiǎn)單的「動(dòng)態(tài)規(guī)劃」其實(shí)就是一個(gè)“打表格”的過程：

先根據(jù) base case 定下來表格中的一些位置的值，再根據(jù)已得出值的位置去推算其他格子的信息。

推算所用到的依賴關(guān)系，也就是我們「暴力遞歸」中的“其余情況”處理邏輯。

動(dòng)態(tài)規(guī)劃的本質(zhì)

動(dòng)態(tài)規(guī)劃的本質(zhì)其實(shí)仍然是枚舉：枚舉所有的方案，并從中找出最優(yōu)解。

但和「暴力遞歸」不同的是，「動(dòng)態(tài)規(guī)劃」少了很多的重復(fù)計(jì)算。

因?yàn)樗蕾嚨倪@些歷史結(jié)果，都被存起來了，因此節(jié)省了大量重復(fù)計(jì)算。

從這一點(diǎn)來說，「動(dòng)態(tài)規(guī)劃」和「記憶化搜索」都是類似的。

要把歷史結(jié)果存起來，必然要使用數(shù)據(jù)結(jié)構(gòu)，在 dp 中我們通常使用一維數(shù)組或者二維數(shù)據(jù)來存儲(chǔ)，假設(shè)是 dp[]。

那么對(duì)應(yīng)解 dp 問題我們有以下過程

1. 狀態(tài)定義 ： 確定 dp[] 中元素的含義，也就是說需要明確 dp[i] 是代表什么內(nèi)容

2. 狀態(tài)轉(zhuǎn)移 ：確定 dp[] 元素之間的關(guān)系，dp[i] 這個(gè)格子是由哪些 dp 格子推算而來的。如斐波那契數(shù)列中就有 dp[i] = dp[i - 1] + dp[i - 2]

3. 起始值 ：base case，dp[] 中的哪些格子是可以直接得出結(jié)果的。如斐波那契數(shù)列中就有 dp[0] = 0 和 dp[1] = 1

消除“后效性”

我們知道使用「動(dòng)態(tài)規(guī)劃」的前提是問題的“無后效性” 。

但是有些時(shí)候問題的“無后效性” 并不容易體現(xiàn)。

需要我們多引入一維來進(jìn)行“消除”。

例如 LeetCode 上經(jīng)典的「股票問題」，使用動(dòng)態(tài)規(guī)劃求解時(shí)往往需要多引入一維表示狀態(tài)，有時(shí)候甚至需要再引入一維代表購買次數(shù)。

注意這里說的消除是帶引號(hào)的，其實(shí)這樣的做法更多的是作為一種“技巧”，它并沒有真正改變問題“后效性” ，只是讓問題看上去變得簡(jiǎn)單的。

“斐波拉契數(shù)列的演變過程是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！