前言

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

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

兩者本質上是一樣的：

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

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

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

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

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

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

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

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

算法分析

1. 傳統(tǒng)遞歸

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

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

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

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

代碼實現如下：

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

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

在遞歸過程中會重復計算已經出現的值，那么此時可以建立一個“記憶”數組來儲存已經遞歸出來的值。如果當前值已經在數組中了就直接返回，無需再計算。

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

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

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

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

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

代碼如下：

總結

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

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

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

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

百度網盤鏈接：https://pan.baidu.com/s/1jxvnKgTsTbkVmjcPGeTm0g

提取碼：2cg8??

?