溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“斐波拉契數列的演變過程是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
經常我們面對一個問題，即使我們明確知道了它是一個“無后效性”問題，它可以通過「動態規劃」來解決。我們還是覺得難以入手。
這時候我的建議是，先寫一個「暴力遞歸」的版本。
還是以剛剛說到的 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);
}
}當我還不知道如何使用「動態規劃」求解時，我會設計一個遞歸函數 recursive() 。
函數傳入矩陣信息和機器人當前所在的位置，返回在這個矩陣里，從機器人所在的位置出發，到達右下角有多少條路徑。
有了這個遞歸函數之后，那問題其實就是求解 recursive(m, n, 0, 0)：求解從 (0,0) 到右下角的路徑數量。
接下來，實現這個函數：
Base case: 由于題目明確了機器人只能往下或者往右兩個方向走，所以可以定下來遞歸方法的 base case 是當已經處于矩陣的最后一行或者最后一列，即只一條路可以走。
其余情況：機器人既可以往右走也可以往下走，所以對于某一個位置來說，到達右下角的路徑數量等于它右邊位置到達右下角的路徑數量 + 它下方位置到達右下角的路徑數量。即 recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1)，這兩個位置都可以通過遞歸函數進行求解。
其實到這里，我們已經求解了這個問題了。
但這種做法還有個嚴重的性能問題。
如果將我們上述的代碼提交到 LeetCode，會得到 timeout 的結果。
可見「暴力遞歸」的解決方案“很慢”。
我們知道所有遞歸函數的本質都是“壓棧”和“彈棧”。
既然這個過程很慢，我們可以通過將遞歸版本暴力解法的改為非遞歸的暴力解法，來解決 timeout 的問題嗎？
答案是不行，因為導致 timeout 的原因不在于使用“遞歸”手段所帶來的成本。
而在于在計算過程，我們進行了多次的重復計算。
我們嘗試展開遞歸過程第幾步來看看：
不難發現，在遞歸展開過程會遇到很多的重復計算。
隨著我們整個遞歸過程的展開，重復計算的次數會呈倍數增長。
這才是「暴力遞歸」解決方案“慢”的原因。
既然是重復計算導致的 timeout，我們自然會想到將計算結果進行“緩存”的方案：
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];
}
}對「暴力遞歸」過程中的中間結果進行緩存，確保相同的情況只會被計算一次的做法，稱為「記憶化搜索」。
做了這樣的改進之后，提交 LeetCode 已經能 AC 并得到一個不錯的評級了。
我們再細想一下就會發現，其實整個求解過程，對于每個情況（每個點）的訪問次數并沒有發生改變。
只是從「以前的每次訪問都進行求解」改進為「只有第一次訪問才真正求解」。
事實上，我們通過查看 recursive() 方法就可以發現：
當我們求解某一個點 (i, j) 的答案時，其實是依賴于 (i, j + 1) 和 (i + 1, j) 。
也就是每求解一個點的答案，都需要訪問兩個點的結果。
這種情況是由于我們采用的是“自頂向下”的解決思路所導致的。
我們無法直觀確定哪個點的結果會在什么時候被訪問，被訪問多少次。
所以我們不得不使用一個與矩陣相同大小的數組，將所有中間結果“緩存”起來。
換句話說，「記憶化搜索」解決的是重復計算的問題，并沒有解決結果訪問時機和訪問次數的不確定問題。
關于「記憶化搜索」最后再說一下。
網上有不少博客和資料在編寫「記憶化搜索」解決方案時，會編寫類似如下的代碼：
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];
}
}可以和我上面提供的解決方案作對比。主要區別在于 if (cache[i][j] == -1) 的判斷里面。
在我提供解決方案中，會在計算 cache[i][j] 時，嘗試從“緩存”中讀取 cache[i + 1][j] 和 cache[i][j + 1]，確保每次調用 recursive() 都是必須的，不重復的。
網上大多數的解決方案只會在外層讀取“緩存”，在真正計算 cache[i][j] 的時候并不采取先檢查再調用的方式，直接調用 recursive() 計算子問題 。
雖然兩者相比與直接的「暴力遞歸」都大大減少了計算次數（recursive() 的訪問次數），但后者的計算次數顯然要比前者高上不少。
你可能會覺得反正都是“自頂向下”，兩者應該沒有區別吧？
為此我提供了以下實驗代碼來比較它們對 recursive() 的調用次數：
class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
solution.uniquePaths(15, 15);
}
private int[][] cache;
private long count; // 統計 遞歸函數 的調用次數 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);
}
}因為我們使用 cache 數組的目的是減少 recursive() 函數的調用。
只有確保在每次調用 recursive() 之前先去 cache 數組檢查，我們才可以將對 recursive() 函數的調用次數減到最少。
在數據為 15 的樣本下，這是 O(393n) 和 O(224n) 的區別，但對于一些卡常數特別嚴重的 OJ，尤其重要。
所以我建議你在「記憶化搜索」的解決方案時，采取與我一樣的策略：
確保在每次訪問遞歸函數時先去“緩存”檢查。盡管這有點“不美觀”，但它能發揮「記憶化搜索」的最大作用。
你可能會想，為什么我們需要改進「記憶化搜索」，為什么需要明確中間結果的訪問時機和訪問次數？
因為一旦我們能明確中間結果的訪問時機和訪問次數，將為我們的算法帶來巨大的提升空間。
前面說到，因為我們無法確定中間結果的訪問時機和訪問次數，所以我們不得不“緩存”全部中間結果。
但如果我們能明確中間結果的訪問時機和訪問次數，至少我們可以大大降低算法的空間復雜度。
這就涉及解決思路的轉換：從「自頂向下」到「自底向上」 。
如何實現從「自頂向下」到「自底向上」的轉變，還是通過具體的例子來理解。
這是 LeetCode 509. Fibonacci Number，著名的“斐波那契數列”問題。
如果不了解什么是“斐波那契數列”，可以查看對應的 維基百科。
由于斐波那契公式為：
天然適合使用遞歸：
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];
}
}但這仍然會有我們之前所說的問題，這些問題都是因為直接遞歸是“自頂向下”所導致的。
這樣的解法的時空復雜度為 O(n) ：每個值計算一次，使用了長度為 n + 1 的數組。
通過觀察斐波那契公式，我們可以發現要計算某個 n ，只需要知道 n - 1 的解和 n - 2 的解。
同時 n = 1 和 n = 2 的解又是已知的（base case）。
所以我們大可以從 n = 3 出發，逐步往后迭代得出 n 的解。
由于計算某個值的解，只依賴該值的前一位的解和前兩位的解，所以我們只需要使用幾個變量緩存最近的中間結果即可：
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;
}
}這樣我們就把原本空間復雜度為 O(N) 的算法降低為 O(1) ：只是用了幾個有限的變量。
但不是所有的「動態規劃」都像“斐波那契數列”那么簡單就能實現從“自頂向下”到“自底向上”的轉變。
當然也不是毫無規律可循，尤其是我們已經寫出了「暴力遞歸」的解決方案。
讓我們再次回到 LeetCode 62. Unique Paths 當中：
class Solution {
public int uniquePaths(int m, int n) {
// 由于我們的「暴力遞歸」函數，真正的可變參數就是 i 和 j（ 變化范圍分別是 [0,m-1] 和 [0, n-1] ） // 所以建議一個二維的 dp 數組進行結果存儲（相當于建一個表格） int[][] dp = new int[m][n];
// 根據「暴力遞歸」函數中的 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;
// 根據「暴力遞歸」函數中對其他情況的處理邏輯（依賴關系）編寫循環 //（根據表格的最后一行和最后一列的值，得出表格的其他格子的值） 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]（表格中左上角的位置，也就起點的值） return dp[0][0];
// 原「暴力遞歸」調用 // 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);
}
}不難發現，我們甚至可以直接根據「暴力遞歸」來寫出「動態規劃」，而不需要關心原問題是什么。
簡單的「動態規劃」其實就是一個“打表格”的過程：
先根據 base case 定下來表格中的一些位置的值，再根據已得出值的位置去推算其他格子的信息。
推算所用到的依賴關系，也就是我們「暴力遞歸」中的“其余情況”處理邏輯。
動態規劃的本質其實仍然是枚舉：枚舉所有的方案，并從中找出最優解。
但和「暴力遞歸」不同的是，「動態規劃」少了很多的重復計算。
因為所依賴的這些歷史結果，都被存起來了，因此節省了大量重復計算。
從這一點來說，「動態規劃」和「記憶化搜索」都是類似的。
要把歷史結果存起來，必然要使用數據結構，在 dp 中我們通常使用一維數組或者二維數據來存儲，假設是 dp[]。
那么對應解 dp 問題我們有以下過程
狀態定義 ： 確定 dp[] 中元素的含義，也就是說需要明確 dp[i] 是代表什么內容
狀態轉移 ：確定 dp[] 元素之間的關系，dp[i] 這個格子是由哪些 dp 格子推算而來的。如斐波那契數列中就有 dp[i] = dp[i - 1] + dp[i - 2]
起始值 ：base case，dp[] 中的哪些格子是可以直接得出結果的。如斐波那契數列中就有 dp[0] = 0 和 dp[1] = 1
我們知道使用「動態規劃」的前提是問題的“無后效性” 。
但是有些時候問題的“無后效性” 并不容易體現。
需要我們多引入一維來進行“消除”。
例如 LeetCode 上經典的「股票問題」，使用動態規劃求解時往往需要多引入一維表示狀態，有時候甚至需要再引入一維代表購買次數。
注意這里說的消除是帶引號的，其實這樣的做法更多的是作為一種“技巧”，它并沒有真正改變問題“后效性” ，只是讓問題看上去變得簡單的。
“斐波拉契數列的演變過程是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
