記憶化搜尋（Memory search）心理學是指搜尋信息的流程，但是搜尋到的一些解用動態規劃的那種思想和模式作一些保存。
基本介紹
- 中文名：記憶化搜尋
- 外文名：Memory search
- 性質：動態規劃
- 屬性：名詞
簡介,套用,
簡介
一般說來，動態規劃總要遍歷所有的狀態，而搜尋可以排除一些無效狀態。更重要的是搜尋還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。記憶化算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜尋和動態規劃兩方面的優點，因而還是很有實用價值的。
套用
題目描述：已知n個slots，1<n<17，每個slot有一個height，height的值有四種，分別為{1,2,3,4}.給你n個slot的，必須滿足以下兩個條件，求有多少種情況.
一：必須有兩個相鄰的slot的差為3，即一個為4，一個為1.
二：必須有三種不同的height值.
Sample Input
2
3
-1
Sample Output
2: 0
3: 8
這道題有組合公式，但想推出來不容易，其實用搜尋就能很好地解決。
如果用暴搜的話，當n>10就會逾時。這時，很容易想到動態規劃，但DP不僅需要推出狀態轉移方程式，還要進行拓撲排序，對於這題，很難用傳統的DP解決。
雖然不能使用傳統意義上的動態規劃解決本題，但動態規劃的思想仍然能起到作用。搜尋相對於動態規劃最大的劣勢無非就是重複計運算元結構，所以我們在搜尋的過程中，對於每一個子結構只計算一次，之後保存到數組裡，以後要用到的時候直接調用就可以了，這就是我要介紹的記憶化搜尋。
記憶化搜尋的實質是動態規劃,效率也和動態規劃接近，形式是搜尋,簡單直觀，代碼也容易編寫，不需要進行什麼拓撲排序了。
可以歸納為：記憶化搜尋=搜尋的形式+動態規劃的思想
對於狀態的存儲，可用數組num[a] [b][c][d]，其中a為還剩幾個，b為找到了哪幾個，c為找到的最後一個數，d表示是否已經出現1，4相連的兩數。
這樣不需要任何其他的最佳化，程式就能0ms得到AC。
