一、重疊子問題

斐波那契數(shù)列沒有求最值的問題，因此嚴(yán)格來說它不是最優(yōu)解問題，當(dāng)然也就不是動(dòng)態(tài)規(guī)劃問題。但它能幫助你理解什么是重疊子問題。首先，它的數(shù)學(xué)形式即遞歸表達(dá)是這樣的：

def Fibonacci(n):if (n == 0 or n == 1):return nif (n > 1):return Fibonacci(n - 1) + Fibonacci(n - 2)def main():result = Fibonacci(4)print(result)if __name__ == "__main__":main()

這個(gè)代碼本身沒有問題, 但是它的效率極低。假設(shè)上面的函數(shù)調(diào)用輸入是10，把遞歸樹畫出來:

如果要計(jì)算原問題F(10), 就需要先計(jì)算出問題F(9)和F(8), 如果要計(jì)算F(9), 就需要先計(jì)算出子問題F(8) 和 F(7)，以此類推。這個(gè)遞歸的終止條件是當(dāng)F(1)=1 或 F(0)=0時(shí)結(jié)束。

看完斐波那契數(shù)列的求解樹之后，就會(huì)發(fā)現(xiàn)問題:

• 用紅色標(biāo)出的兩個(gè)區(qū)域中，它們的遞歸計(jì)算過程完全相同

這意味著，第2個(gè)紅色區(qū)域的計(jì)算是 “完全沒有必要的”，它是重復(fù)的計(jì)算。因?yàn)槲覀円呀?jīng)在求解F(7)的時(shí)候把F(6)的所有情況算過了。因此我們把第2個(gè)紅色區(qū)域的計(jì)算稱為重疊子問題。

二、使用備忘錄解決重復(fù)問題

既然存在重復(fù)的子問題，那我們?cè)谟龅竭@些重復(fù)的子問題時(shí)，只需要執(zhí)行一次即可，即消滅重復(fù)計(jì)算的過程。

我們可以創(chuàng)建一個(gè)備忘錄（memorization），在每次計(jì)算出某個(gè)子問題的答案后，將這個(gè)臨時(shí)的中間結(jié)果記錄到備忘錄里，然后再返回。

接著，每當(dāng)遇到一個(gè)子問題時(shí)，我們不是按照原有的思路開始對(duì)子問題進(jìn)行遞歸求解，而是先去這個(gè)備忘錄中查詢一下。如果發(fā)現(xiàn)之前已經(jīng)解決過這個(gè)子問題了，那么就直接把答案取出來復(fù)用，沒有必要再遞歸下去耗時(shí)的計(jì)算了。

對(duì)于備忘錄，可以考慮使用以下兩種數(shù)據(jù)結(jié)構(gòu)：

• 數(shù)組（Array），通常對(duì)于簡(jiǎn)單的問題來說，使用一維數(shù)組就足夠了。
• 哈希表（Hash table），如果你存儲(chǔ)的狀態(tài)不能直接通過索引找到需要的值（比如斐波那契數(shù)列問題，你可以直接通過數(shù)組的索引確定其對(duì)應(yīng)子問題的解是否存在，如果存在你就拿出來直接使用），比如你使用了更高級(jí)的數(shù)據(jù)結(jié)構(gòu)而非簡(jiǎn)單的數(shù)字索引，那么你還可以考慮使用哈希表，即字典來存儲(chǔ)中間狀態(tài)，來避免重復(fù)計(jì)算的問題。

下面看看用數(shù)組實(shí)現(xiàn)的備忘錄來解決斐波那契數(shù)列的代碼：

def Fibonacci(n, memo):if (n == 0 or n == 1):return n# 如果備忘錄中找到了之前計(jì)算的結(jié)果，那就直接返回，避免重復(fù)計(jì)算if (memo[n] != None):return memo[n]if (n > 1):memo[n] = Fibonacci(n - 1, memo) + Fibonacci(n - 2, memo)return memo[n]# 如果數(shù)值無效(比如 < 0)，則返回0return 0def FibonacciAdvance(n):memo = [None] * (n + 1)return Fibonacci(n, memo)def main():result = FibonacciAdvance(4)print(result)if __name__ == "__main__":main()

實(shí)際上，這就是我們所熟知的“剪枝與優(yōu)化”，把一棵存在巨量冗余的遞歸樹通過剪枝，改造成了一幅不存在冗余的遞歸圖，極大減少了子問題（即遞歸圖中節(jié)點(diǎn)）的個(gè)數(shù)。通過這種方式，我們大幅縮減了算法的計(jì)算量，因?yàn)樗兄貜?fù)的部分都被跳過了

三、重疊子問題的限制

有些問題雖然看起來像包含“重疊子問題”的子問題，但是這類子問題可能具有后效性，但我們追求的是無后效性。
所謂無后效性，指的是在通過 A 階段的子問題推導(dǎo) B 階段的子問題的時(shí)候，我們不需要回過頭去再根據(jù) B 階段的子問題重新推導(dǎo) A 階段的子問題，即子問題之間的依賴是單向性的。
換句話說，如果一個(gè)問題可以通過重疊子問題緩存進(jìn)行優(yōu)化，那么它肯定都能被畫成一棵樹。

四、方法的弊端

通過重疊子問題緩存可以極大加速我們的代碼執(zhí)行效率。但是凡事都有兩面性，毋庸置疑，這種方案肯定是通過某種犧牲換取了性能的提升。
在硬幣找零問題中，我們就可以利用備忘錄來避免重復(fù)計(jì)算。但這樣有個(gè)問題，如果我們的錢幣總額數(shù)量非常巨大，那這個(gè)數(shù)組的大小就會(huì)非常巨大，導(dǎo)致的結(jié)果就是會(huì)占據(jù)大量的內(nèi)存存儲(chǔ)空間，而且有很多的數(shù)字其實(shí)是不會(huì)被求解的，存在很多的“存儲(chǔ)空洞”。顯然，這是一種浪費(fèi)。
所以在解題的過程中，你需要根據(jù)實(shí)際情況，在空間和時(shí)間中尋求一個(gè)平衡，將這個(gè)問題考慮在內(nèi)。

五、總結(jié)與升華

備忘錄的思想極為重要，特別是當(dāng)求解的問題包含重疊子問題時(shí)，只要問題包含重復(fù)計(jì)算，你就應(yīng)該考慮使用備忘錄來對(duì)算法時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)化。具體來說，備忘錄解法可以歸納為：
1.用數(shù)組或哈希表來緩存已解的子問題答案，并使用自頂向下的遞歸順序遞歸數(shù)據(jù)；
2.基于遞歸實(shí)現(xiàn)，與暴力遞歸的區(qū)別在于備忘錄為每個(gè)求解過的子問題建立了備忘錄（緩存）；
3.為每個(gè)子問題的初始記錄存入一個(gè)特殊的值，表示該子問題尚未求解；
4.在求解過程中，從備忘錄中查詢。如果未找到或是特殊值，表示未求解；否則取出該子問題的答案，直接返回。

總結(jié)

以上是生活随笔為你收集整理的解决递归中的重复计算问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。