1樓：RuiruiOfficial
一些比較粗淺的理解：
遞迴搜尋 + 記憶快取 = 記憶化搜尋
記憶化搜尋 + 快取可有序求解 + 迭代填充記憶 = 動態規劃動態規劃 + 即時廢棄不需要的記憶 = 狀態壓縮動態規劃
2樓：餃子龍
@interestingLSY大佬的這篇部落格我認為講的很詳細，還有疑問的話可以看下。
聊聊動態規劃與記憶化搜尋
段落節選：
總結一下：
記憶化搜尋和動態規劃從根本上來講就是乙個東西,**(印象中)任何乙個 dp 方程都能轉為記憶化搜尋 ，反之亦然（為什麼？見下文「體現在」的第四條）
體現在根據記憶化搜尋的引數可以直接得到dp的狀態，反之亦然
根據記憶化搜尋的遞迴關係可以寫出狀態轉移方程，這個方程可以直接寫出迴圈式的dp，只不過是反的(想想為什麼？)，反之亦然
大部分記憶化搜尋時空複雜度與不加優化的dp 完全相同
最重要的一點：二者思想類似！！ 核心思想均為：
利用對於相同引數答案相同的特性，對於相同的引數（迴圈式的dp體現為陣列下標），記錄其答案，免去重複計算，從而起到優化時間複雜度的作用。這，便是二者的精髓。**
建議好好想想第四條。記住，學乙個演算法，一定要理解他的精髓。
3樓：啦啦啦
我目前的知識水平認為。
如果從概念上來說 dp是從區域性最優到整體最優。 記憶話搜尋是通過之前求的最優解來計算目前的最優解。本質上還是dp
但是從考慮問題的角度來看，有不是dp，
記憶話搜尋一般都是考慮之前的狀態在後面是否重新計算了一遍，如果是就儲存，避免重複造輪子。
dp 一般都是考慮如何猜出 dp轉移方程。
目前我是這樣認為的。等我那天又有了新的了解再來更新。
4樓：櫻花記憶
準確地來說，記憶化搜尋是動態規劃（DP思想）的一種實現形式，兩者是真包含關係，希望題主不要混淆這兩個概念。
那麼回到問題本身，我猜題主真正想問的是：遞推與記憶化搜尋是否等價？
曾經我也這麼認為，但在OJ刷了一些題之後，我發現在某些特定的情況下，遞推和記憶化搜尋並不能相互轉化，例如：
第一種情況：記憶化搜尋可以實現然而普通遞推不能實現的問題（或實現起來非常麻煩的問題）
最為典型的代表是「滑雪」（POJ 1088）一題。
我們假設f[i][j]表示滑到座標(i,j)所能滑到的最長長度。那麼對於狀態f[i][j]而言，它可以由f[i-1][j],f[i][j-1],f[i+1][j],f[i][j+1]四個狀態推得，然而我們使用普通的遞推（兩個for）只能得到上、左兩個方向的狀態，右、下兩個方向的狀態卻無從得知，因此使用遞推就不能滿足我們的要求，如果再補上兩個for覆蓋右、下狀態，那麼時間複雜度就變為了N^4，很明顯會TLE。
這題如果採用記憶化搜尋，在搜尋的過程中發現f[i][j]在以前的某個時刻已經被計算過，直接return，可以保證時間複雜度為N^2。
還有乙個例子是樹上的動態規劃，通常樹形dp會使用記憶化搜尋來實現，因為比較方便，但也不是不能用遞推（遞推具體的實現方法是，先根據題目要求建圖，然後求出拓撲序列，再根據拓撲序列進行遞推。）
因此，我認為記憶化搜尋通常是用在遞推關係不那麼明確的情況下，使用記憶化可以避免考慮複雜的DP順序。當然，線性的遞推也可以使用記憶化搜尋實現，但是會帶來不必要的系統棧占用，導致程式效能下降。
第二種情況：普通遞推能夠實現而記憶化不能實現的問題
這類問題比較少，但也不是沒有，常見於需要優化（重點）的DP。
在特定問題下，題目對於DP的效率有著較高的要求，時間要求比如單調佇列優化DP、斜率優化DP或者有空間要求（滾動陣列優化），在這種情況下，我們就不得不遞推求解。
比較經典的乙個問題是：01揹包+列印方案
我們都知道01揹包的經典方程是：f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]) , j>=w[i]
使用記憶化搜尋可以實現這個二維的遞推過程，但是如果題目對空間有要求，要求你優化掉物品數量一維（優化這一維在遞推實現中是很容易的），你就會發現記憶化搜尋就出現了很大的問題，因為對於同一剩餘揹包空間容量，可能可以由多個i推得，我們無法控制dp順序，而01揹包的遞推優化正是建立在巧妙地變化列舉順序的基礎上進行的，因此記憶化搜尋也就無能為力了。
5樓：Mr.小祥
如果用「能不能求解」某一問題來區分的話，那還真沒什麼區別。但是在這個意義上，暴力搜尋和他們簡直一模一樣。 事實上，記憶化搜尋與動態規劃只是一種優化效能的手段，的確如你所說的那樣是乙個是自頂向下，另乙個是自底向上。
但是你可以想下：
從上往下的搜尋方式是不是真的會計算所有節點？ 還是會省略一些不必要的節點？
如果記憶化搜尋會展開所有節點鋪滿乙個我們的矩陣，那是不是我們直接自底向上更好？
經常發說說和動態的人與不發說說和動態的人的心裡狀態有什麼不一樣？不發說說的人真的就過的好嗎？
謝不邀不僅不發說說，所有一切個人資訊都僅對自己可見。也沒有因為什麼隱私洩露問題，而是再也沒有想給看的人，一想到他再也看不見了，就覺得沒什麼必要沒什麼興致了 真正優秀的人不會總發說說的，身邊成功的學長學姐都是慢慢蓄力，一鳴驚人，不會這麼透明的什麼都讓別人看到，最多一年也就個位數的總結幾次，而且都特別低...
當年奇虎的社群化搜尋，為什麼沒有成功？
謝達明 奇虎社群搜尋沒有成功的原因上面幾位已經回答的很清楚了，有意思的是，奇虎更像乙個面向公關公司的小眾產品，很多公關公司經常使用奇虎來查詢他們服務客戶的資訊，後來奇虎乾脆推出了基於奇虎搜尋引擎的VoiceTracker輿情分析產品，這其實完全偏離了周鴻禕預期的設想，奇虎社群搜尋淪為乙個副產品是必然...
動態ip與靜態ip的區別？
IPIDEA全球HTTP 目前，隨著網際網路技術的快速發展，主機數以百萬計。為了更好地區分這些主機，在這種情況下，需要給每台主機分配乙個特殊的位址，稱為IP位址。每個主機都可以通過IP位址訪問。一般來說，IP位址主要由四部分數字組成。當然每個部分的數字對應八個二進位制數，每個部分要用小數點分開。目前...