前言

在動(dòng)態(tài)規(guī)劃中，我們通常使用二維數(shù)組來(lái)存儲(chǔ)子問(wèn)題的最優(yōu)解，但是對(duì)于某些問(wèn)題，如果使用二維數(shù)組存儲(chǔ)所有子問(wèn)題的解，可能會(huì)造成空間復(fù)雜度過(guò)高。

這個(gè)時(shí)候我們可以考慮使用**記憶化搜索**來(lái)優(yōu)化空間復(fù)雜度。

算法介紹

記憶化搜索實(shí)際上是用遞歸來(lái)實(shí)現(xiàn)的，但是在遞歸的過(guò)程中有許多結(jié)果是被反復(fù)計(jì)算的，這樣會(huì)大大降低算法的執(zhí)行效率。

而記憶化搜索是在遞歸的過(guò)程中，將已經(jīng)計(jì)算出來(lái)的結(jié)果保存起來(lái)，當(dāng)之后的計(jì)算再次用到時(shí)直接取出結(jié)果，避免重復(fù)運(yùn)算，因此極大的提高了算法的效率。

舉個(gè)例子，比如「斐波那契數(shù)列」的定義是：f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)。如果我們使用遞歸算法求解第 n 個(gè)斐波那契數(shù)，則對(duì)應(yīng)的遞推過(guò)程如下圖所示：

從圖中可以看出：如果使用普通遞歸算法，想要計(jì)算 f(5)，需要先計(jì)算 f(3) 和 f(4)，而在計(jì)算 f(4) 時(shí)還需要計(jì)算 f(3)。這樣 f(3) 就進(jìn)行了多次計(jì)算，同理 f(0)、f(1)、f(2) 都進(jìn)行了多次計(jì)算，從而導(dǎo)致了重復(fù)計(jì)算問(wèn)題。

為了避免重復(fù)計(jì)算，在遞歸的同時(shí)，我們可以使用一個(gè)緩存（數(shù)組或哈希表）來(lái)保存已經(jīng)求解過(guò)的 f(k) 的結(jié)果。如上圖所示，當(dāng)遞歸調(diào)用用到 f(k) 時(shí)，先查看一下之前是否已經(jīng)計(jì)算過(guò)結(jié)果，如果已經(jīng)計(jì)算過(guò)，則直接從緩存中取值返回，而不用再遞推下去，這樣就避免了重復(fù)計(jì)算問(wèn)題。

使用記憶化搜索方法解決斐波那契數(shù)列的代碼如下：

寫(xiě)在最后

記憶化搜索是一種常見(jiàn)的動(dòng)態(tài)規(guī)劃優(yōu)化方法，可以避免重復(fù)計(jì)算，提高算法效率。在使用記憶化搜索時(shí)，我們可以將遞歸算法與緩存技術(shù)結(jié)合起來(lái)，通過(guò)緩存子問(wèn)題的解來(lái)避免重復(fù)計(jì)算，從而節(jié)省時(shí)間和空間復(fù)雜度。

最后送大家一份 JetBrains IDEA 破解教程和干貨，快拿去用吧：

百度網(wǎng)盤(pán)鏈接：https://pan.baidu.com/s/1jxvnKgTsTbkVmjcPGeTm0g

提取碼：2cg8??

?