首先大家要知道，記憶化搜索是動態(tài)規(guī)劃的入門。

什么是記憶化搜索？搜索的低效在于沒有能夠很好地處理重疊子問題；動態(tài)規(guī)劃雖然比較好地處理了重疊子問題，但是在有些拓撲關(guān)系比較復雜的題目面前，又顯得無奈。記憶化搜索正是在這樣的情況下產(chǎn)生的，它采用搜索的形式和動態(tài)規(guī)劃中遞推的思想將這兩種方法有機地綜合在一起，揚長避短，簡單實用，在信息學中有著重要的作用。

用一個公式簡單地說：記憶化搜索=搜索的形式+動態(tài)規(guī)劃的思想。

動態(tài)規(guī)劃：就是一個最優(yōu)化問題，先將問題分解為子問題，并且對于這些分解的子問題自身就是最優(yōu)的才能在這個基礎上得出我們要解決的問題的最優(yōu)方案，要不然的話就能找到一個更優(yōu)的解來替代這個解，得出新的最優(yōu)自問題，這當然是和前提是矛盾的。動態(tài)規(guī)劃不同于 貪心算法，因為貪心算法是從局部最優(yōu)來解決問題，而動態(tài)規(guī)劃是全局最優(yōu)的。用動態(tài)規(guī)劃的時候不可能在子問題還沒有得到最優(yōu)解的情況下就做出決策，而是必須等待子問題得到了最優(yōu)解之后才對當下的情況做出決策，所以往往動態(tài)規(guī)劃都可以用 一個或多個遞歸式來描述。而貪心算法卻是先做出一個決策，然后在去解決子問題。這就是貪心和動態(tài)規(guī)劃的不同。

一般遇到一個動態(tài)規(guī)劃類型的問題，都先要確定最優(yōu)子結(jié)構(gòu)，還有重疊子問題，這兩個是動態(tài)規(guī)劃最大的特征，然后就是要寫 動態(tài)規(guī)劃的狀態(tài)方程，這個步驟十分十分的重要的，寫動歸方程是需要一定的經(jīng)驗的，這可以通過訓練來達到目的。接著就是要自底向上的求解問題的，先將最小規(guī)模的子問題的最優(yōu)解求出，一般都用一張表來記錄下求得的解，到后來遇到同樣的子問題的時候就可以直接查表得到答案，最后就是通過一步一步的迭代得出最后問題的答案了。

動態(tài)規(guī)劃的一種變形就是記憶化搜索，就是根據(jù)動歸方程寫出遞歸式，然后在函數(shù)的開頭直接返回以前計算過的結(jié)果，當然這樣做也需要一個存儲結(jié)構(gòu)記下前面計算過的結(jié)果，所以又稱為記憶化搜索。

記憶化搜索遞歸式動態(tài)規(guī)劃：

（1）記憶化搜索的思想

記憶化搜索的思想是,在搜索過程中，會有很多重復計算,如果我們能記錄一些狀態(tài)的答案，就可以減少重復搜索量

（2）記憶化搜索的適用范圍

根據(jù)記憶化搜索的思想，它是解決重復計算，而不是重復生成，也就是說，這些搜索必須是在搜索擴展路徑的過程中分步計算的題目，也就是“搜索答案與路徑相關(guān)”的題目，而不能是搜索一個路徑之后才能進行計算的題目，必須要分步計算，并且搜索過程中，一個搜索結(jié)果必須可以建立在同類型問題的結(jié)果上，也就是類似于動態(tài)規(guī)劃解決的那種。

也就是說，他的問題表達，不是單純生成一個走步方案，而是生成一個走步方案的代價等，而且每走一步，在搜索樹/圖中生成一個新狀態(tài)，都可以精確計算出到此為止的費用，也就是，可以分步計算，這樣才可以套用已經(jīng)得到的答案

（3）記憶化搜索的核心實現(xiàn)

1. 首先，要通過一個表記錄已經(jīng)存儲下的搜索結(jié)果，一般用哈希表實現(xiàn)

2. 狀態(tài)表示，由于是要用哈希表實現(xiàn)，所以狀態(tài)最好可以用數(shù)字表示，常用的方法是把一個狀態(tài)連寫成一個p進制數(shù)字，然后把這個數(shù)字對應的十進制數(shù)字作為狀態(tài)

3. 在每一狀態(tài)搜索的開始，高效的使用哈希表搜索這個狀態(tài)是否出現(xiàn)過，如果已經(jīng)做過，直接調(diào)用答案，回溯

4. 如果沒有，則按正常方法搜索

（4）記憶化搜索是類似于動態(tài)規(guī)劃的，不同的是，它是倒做的“遞歸式動態(tài)規(guī)劃”。