前言

在解算法題時，經(jīng)?？吹胶芏囝}解中將動態(tài)規(guī)劃與記憶化搜索并列介紹，那么他們之間到底存在怎樣的關(guān)系？記憶化搜索的方式到底算不算動態(tài)規(guī)劃？又或者說他們是不是同一種東西呢？下面就讓我們一起來探索下吧！

記憶化搜索 vs 狹義動態(tài)規(guī)劃

兩者本質(zhì)上是一樣的：

都有重疊子問題，且相比暴力求解，使用這兩種方法進行優(yōu)化的目的是要跳過這些重疊子問題；

都有 base case 和狀態(tài)轉(zhuǎn)移方程。

區(qū)別主要有五點：

記憶化搜索的編程模式是遞歸，而狹義動態(tài)規(guī)劃的編程模式是遞推。一般來說，在相同計算量下，因為需要不斷調(diào)用函數(shù)，遞歸的開銷要比遞推更大；

記憶化搜索是自頂向下求解，從目標狀態(tài)到邊界條件；而狹義動態(tài)規(guī)劃是自底向上，從邊界條件到目標狀態(tài)；

記憶化搜索不需要嚴格設(shè)計好計算順序，備忘錄沒有記錄則進行計算即可；而動態(tài)規(guī)劃必須分析已有的 base case，嚴格設(shè)計 DP table 的遞推計算順序；

記憶化搜索是以使用備忘錄避免重復(fù)計算來跳過重疊子問題的，而狹義動態(tài)規(guī)劃是以設(shè)計巧妙的遞推順序來壓根就不產(chǎn)生重疊子問題的。

多個狀態(tài)下，動態(tài)規(guī)劃通常會生成大量無效的狀態(tài)，而記憶化搜索則不會，這是記憶化搜索在速度上有可能超越狹義動態(tài)規(guī)劃的地方。

算法分析

1. 傳統(tǒng)遞歸

在記憶化搜索和動態(tài)規(guī)劃之前，我們先來了解下傳統(tǒng)遞歸，首先來看第一個例子，斐波那契數(shù)列。

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……

斐波那契數(shù)列以如下被以遞推的方法定義：

$\ce{F(1)=1，F(xiàn)(2)=1,F(n)=F(n?1)+F(n?2)（n≥3，n∈N^?）}$

代碼實現(xiàn)如下：

上述代碼提交后，會發(fā)現(xiàn)到計算到41時，已經(jīng)超出時間限制，原因在于會重復(fù)計算已經(jīng)出現(xiàn)的值，所以遞歸的最大缺點就是大量的重復(fù)計算，時間復(fù)雜度高。

2. 記憶化遞歸（自頂向下）

在遞歸過程中會重復(fù)計算已經(jīng)出現(xiàn)的值，那么此時可以建立一個“記憶”數(shù)組來儲存已經(jīng)遞歸出來的值。如果當(dāng)前值已經(jīng)在數(shù)組中了就直接返回，無需再計算。

原理： 在遞歸法的基礎(chǔ)上，新建一個長度為 n 的數(shù)組，用于在遞歸時存儲 f(0) 至 f(n) 的數(shù)字值，重復(fù)遇到某數(shù)字則直接從數(shù)組取用，避免了重復(fù)的遞歸計算。

缺點： 記憶化存儲需要使用 O(N) 的額外空間。

其實就是以空間換時間，改進代碼如下：

3. 動態(tài)規(guī)劃（自底向上）

在記憶化遞歸中，已經(jīng)能夠解決時間復(fù)雜度的問題了，但額外增加了空間，若在此優(yōu)化空間復(fù)雜度使用動態(tài)規(guī)劃即可解決。一般來說，只要遞歸能夠解決的動態(tài)規(guī)劃就一定能夠解決，使用動態(tài)規(guī)劃方法實現(xiàn)時間和空間的優(yōu)化。

代碼如下：

總結(jié)

兩者本質(zhì)上是一樣的，但是編程形式上有所不同。

記憶化搜索使用備忘錄記錄狀態(tài)，使用dp()函數(shù)進行狀態(tài)轉(zhuǎn)移；

狹義動態(tài)規(guī)劃使用 DP table 記錄狀態(tài)，使用遞推迭代進行狀態(tài)轉(zhuǎn)移。

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

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

提取碼：2cg8??

?