記憶化搜索

一般説來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。記憶化算法在求解的時候還是按着自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。

題目描述：已知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。