前言

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

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

算法介紹

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

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

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

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

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

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

寫在最后

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

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

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

提取碼：2cg8??

?