本篇內(nèi)容介紹了“斐波拉契數(shù)列的演變過(guò)程是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
10年積累的網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶(hù)對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶(hù)得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有定邊免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
經(jīng)常我們面對(duì)一個(gè)問(wèn)題，即使我們明確知道了它是一個(gè)“無(wú)后效性”問(wèn)題，它可以通過(guò)「動(dòng)態(tài)規(guī)劃」來(lái)解決。我們還是覺(jué)得難以入手。
這時(shí)候我的建議是，先寫(xiě)一個(gè)「暴力遞歸」的版本。
還是以剛剛說(shuō)到的 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ù)之后，那問(wèn)題其實(shí)就是求解 recursive(m, n, 0, 0)：求解從 (0,0) 到右下角的路徑數(shù)量。
接下來(lái)，實(shí)現(xiàn)這個(gè)函數(shù)：
Base case: 由于題目明確了機(jī)器人只能往下或者往右兩個(gè)方向走，所以可以定下來(lái)遞歸方法的 base case 是當(dāng)已經(jīng)處于矩陣的最后一行或者最后一列，即只一條路可以走。
其余情況：機(jī)器人既可以往右走也可以往下走，所以對(duì)于某一個(gè)位置來(lái)說(shuō)，到達(dá)右下角的路徑數(shù)量等于它右邊位置到達(dá)右下角的路徑數(shù)量 + 它下方位置到達(dá)右下角的路徑數(shù)量。即 recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1)，這兩個(gè)位置都可以通過(guò)遞歸函數(shù)進(jìn)行求解。
其實(shí)到這里，我們已經(jīng)求解了這個(gè)問(wèn)題了。
但這種做法還有個(gè)嚴(yán)重的性能問(wèn)題。
如果將我們上述的代碼提交到 LeetCode，會(huì)得到 timeout 的結(jié)果。
可見(jiàn)「暴力遞歸」的解決方案“很慢”。
我們知道所有遞歸函數(shù)的本質(zhì)都是“壓?！焙汀皬棗！?。
既然這個(gè)過(guò)程很慢，我們可以通過(guò)將遞歸版本暴力解法的改為非遞歸的暴力解法，來(lái)解決 timeout 的問(wèn)題嗎？
答案是不行，因?yàn)閷?dǎo)致 timeout 的原因不在于使用“遞歸”手段所帶來(lái)的成本。
而在于在計(jì)算過(guò)程，我們進(jìn)行了多次的重復(fù)計(jì)算。
我們嘗試展開(kāi)遞歸過(guò)程第幾步來(lái)看看：
不難發(fā)現(xiàn)，在遞歸展開(kāi)過(guò)程會(huì)遇到很多的重復(fù)計(jì)算。
隨著我們整個(gè)遞歸過(guò)程的展開(kāi)，重復(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ì)「暴力遞歸」過(guò)程中的中間結(jié)果進(jìn)行緩存，確保相同的情況只會(huì)被計(jì)算一次的做法，稱(chēng)為「記憶化搜索」。
做了這樣的改進(jìn)之后，提交 LeetCode 已經(jīng)能 AC 并得到一個(gè)不錯(cuò)的評(píng)級(jí)了。
我們?cè)偌?xì)想一下就會(huì)發(fā)現(xiàn)，其實(shí)整個(gè)求解過(guò)程，對(duì)于每個(gè)情況（每個(gè)點(diǎn)）的訪(fǎng)問(wèn)次數(shù)并沒(méi)有發(fā)生改變。
只是從「以前的每次訪(fǎng)問(wèn)都進(jìn)行求解」改進(jìn)為「只有第一次訪(fǎng)問(wèn)才真正求解」。
事實(shí)上，我們通過(guò)查看 recursive() 方法就可以發(fā)現(xiàn)：
當(dāng)我們求解某一個(gè)點(diǎn) (i, j) 的答案時(shí)，其實(shí)是依賴(lài)于 (i, j + 1) 和 (i + 1, j) 。
也就是每求解一個(gè)點(diǎn)的答案，都需要訪(fǎng)問(wèn)兩個(gè)點(diǎn)的結(jié)果。
這種情況是由于我們采用的是“自頂向下”的解決思路所導(dǎo)致的。
我們無(wú)法直觀確定哪個(gè)點(diǎn)的結(jié)果會(huì)在什么時(shí)候被訪(fǎng)問(wèn)，被訪(fǎng)問(wèn)多少次。
所以我們不得不使用一個(gè)與矩陣相同大小的數(shù)組，將所有中間結(jié)果“緩存”起來(lái)。
換句話(huà)說(shuō)，「記憶化搜索」解決的是重復(fù)計(jì)算的問(wèn)題，并沒(méi)有解決結(jié)果訪(fǎng)問(wèn)時(shí)機(jī)和訪(fǎng)問(wèn)次數(shù)的不確定問(wèn)題。
關(guān)于「記憶化搜索」最后再說(shuō)一下。
網(wǎng)上有不少博客和資料在編寫(xiě)「記憶化搜索」解決方案時(shí)，會(huì)編寫(xiě)類(lèi)似如下的代碼：
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ì)算子問(wèn)題 。
雖然兩者相比與直接的「暴力遞歸」都大大減少了計(jì)算次數(shù)（recursive() 的訪(fǎng)問(wèn)次數(shù)），但后者的計(jì)算次數(shù)顯然要比前者高上不少。
你可能會(huì)覺(jué)得反正都是“自頂向下”，兩者應(yīng)該沒(méi)有區(qū)別吧？
為此我提供了以下實(shí)驗(yàn)代碼來(lái)比較它們對(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í)，采取與我一樣的策略：
確保在每次訪(fǎng)問(wèn)遞歸函數(shù)時(shí)先去“緩存”檢查。盡管這有點(diǎn)“不美觀”，但它能發(fā)揮「記憶化搜索」的最大作用。
你可能會(huì)想，為什么我們需要改進(jìn)「記憶化搜索」，為什么需要明確中間結(jié)果的訪(fǎng)問(wèn)時(shí)機(jī)和訪(fǎng)問(wèn)次數(shù)？
因?yàn)橐坏┪覀兡苊鞔_中間結(jié)果的訪(fǎng)問(wèn)時(shí)機(jī)和訪(fǎng)問(wèn)次數(shù)，將為我們的算法帶來(lái)巨大的提升空間。
前面說(shuō)到，因?yàn)槲覀儫o(wú)法確定中間結(jié)果的訪(fǎng)問(wèn)時(shí)機(jī)和訪(fǎng)問(wèn)次數(shù)，所以我們不得不“緩存”全部中間結(jié)果。
但如果我們能明確中間結(jié)果的訪(fǎng)問(wèn)時(shí)機(jī)和訪(fǎng)問(wèn)次數(shù)，至少我們可以大大降低算法的空間復(fù)雜度。
這就涉及解決思路的轉(zhuǎn)換：從「自頂向下」到「自底向上」 。
如何實(shí)現(xiàn)從「自頂向下」到「自底向上」的轉(zhuǎn)變，還是通過(guò)具體的例子來(lái)理解。
這是 LeetCode 509. Fibonacci Number，著名的“斐波那契數(shù)列”問(wèn)題。
如果不了解什么是“斐波那契數(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ì)有我們之前所說(shuō)的問(wèn)題，這些問(wèn)題都是因?yàn)橹苯舆f歸是“自頂向下”所導(dǎo)致的。
這樣的解法的時(shí)空復(fù)雜度為 O(n) ：每個(gè)值計(jì)算一次，使用了長(zhǎng)度為 n + 1 的數(shù)組。
通過(guò)觀察斐波那契公式，我們可以發(fā)現(xiàn)要計(jì)算某個(gè) n ，只需要知道 n - 1 的解和 n - 2 的解。
同時(shí) n = 1 和 n = 2 的解又是已知的（base case）。
所以我們大可以從 n = 3 出發(fā)，逐步往后迭代得出 n 的解。
由于計(jì)算某個(gè)值的解，只依賴(lài)該值的前一位的解和前兩位的解，所以我們只需要使用幾個(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)然也不是毫無(wú)規(guī)律可循，尤其是我們已經(jīng)寫(xiě)出了「暴力遞歸」的解決方案。
讓我們?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ì)其他情況的處理邏輯（依賴(lài)關(guān)系）編寫(xiě)循環(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ù)「暴力遞歸」來(lái)寫(xiě)出「動(dòng)態(tài)規(guī)劃」，而不需要關(guān)心原問(wèn)題是什么。
簡(jiǎn)單的「動(dòng)態(tài)規(guī)劃」其實(shí)就是一個(gè)“打表格”的過(guò)程：
先根據(jù) base case 定下來(lái)表格中的一些位置的值，再根據(jù)已得出值的位置去推算其他格子的信息。
推算所用到的依賴(lài)關(guān)系，也就是我們「暴力遞歸」中的“其余情況”處理邏輯。
動(dòng)態(tài)規(guī)劃的本質(zhì)其實(shí)仍然是枚舉：枚舉所有的方案，并從中找出最優(yōu)解。
但和「暴力遞歸」不同的是，「動(dòng)態(tài)規(guī)劃」少了很多的重復(fù)計(jì)算。
因?yàn)樗蕾?lài)的這些歷史結(jié)果，都被存起來(lái)了，因此節(jié)省了大量重復(fù)計(jì)算。
從這一點(diǎn)來(lái)說(shuō)，「動(dòng)態(tài)規(guī)劃」和「記憶化搜索」都是類(lèi)似的。
要把歷史結(jié)果存起來(lái)，必然要使用數(shù)據(jù)結(jié)構(gòu)，在 dp 中我們通常使用一維數(shù)組或者二維數(shù)據(jù)來(lái)存儲(chǔ)，假設(shè)是 dp[]。
那么對(duì)應(yīng)解 dp 問(wèn)題我們有以下過(guò)程
狀態(tài)定義 ： 確定 dp[] 中元素的含義，也就是說(shuō)需要明確 dp[i] 是代表什么內(nèi)容
狀態(tài)轉(zhuǎn)移 ：確定 dp[] 元素之間的關(guān)系，dp[i] 這個(gè)格子是由哪些 dp 格子推算而來(lái)的。如斐波那契數(shù)列中就有 dp[i] = dp[i - 1] + dp[i - 2]
起始值 ：base case，dp[] 中的哪些格子是可以直接得出結(jié)果的。如斐波那契數(shù)列中就有 dp[0] = 0 和 dp[1] = 1
我們知道使用「動(dòng)態(tài)規(guī)劃」的前提是問(wèn)題的“無(wú)后效性” 。
但是有些時(shí)候問(wèn)題的“無(wú)后效性” 并不容易體現(xiàn)。
需要我們多引入一維來(lái)進(jìn)行“消除”。
例如 LeetCode 上經(jīng)典的「股票問(wèn)題」，使用動(dòng)態(tài)規(guī)劃求解時(shí)往往需要多引入一維表示狀態(tài)，有時(shí)候甚至需要再引入一維代表購(gòu)買(mǎi)次數(shù)。
注意這里說(shuō)的消除是帶引號(hào)的，其實(shí)這樣的做法更多的是作為一種“技巧”，它并沒(méi)有真正改變問(wèn)題“后效性” ，只是讓問(wèn)題看上去變得簡(jiǎn)單的。
“斐波拉契數(shù)列的演變過(guò)程是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
