記憶化搜尋

記憶化搜尋它採用搜尋的形式和動態規劃中遞推的思想將這兩種方法有機地綜合在一起，揚長避短，簡單實用，在信息學中有著重要的作用。用一個公式簡單地說：記憶化搜尋=搜尋的形式+動態規劃的思想。

記憶化搜尋：算法上依然是搜尋的流程，但是搜尋到的一些解用動態規劃的那種思想和模式作一些保存。
一般說來，動態規劃總要遍歷所有的狀態，而搜尋可以排除一些無效狀態。
更重要的是搜尋還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
記憶化算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，
以後再次遇到這個狀態的時候，就不必重新求解了。
這種方法綜合了搜尋和動態規劃兩方面的優點，因而還是很有實用價值的。
上傳/更換附屬檔案動態規劃的另一種實現形式——記憶化搜尋的套用
題目描述：已知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&#91;a&#93; &#91;c&#93;&#91;d&#93;，其中a為還剩幾個，b為找到了哪幾個，c為找到的最後一個數，d表示是否已經出現1，4相連的兩數。
這樣不需要任何其他的最佳化，程式就能0ms得到AC.