動態規劃解決排列問題

Question

我有四個數字，「1」，「2」，「3」，「4」。

該程序的輸入是一個整數，只能包含上述4位數字。將會有很多投入。的輸入

實施例：1123，4123，4444

我需要計算給定輸入粘附到下面的規則的排列的數量：

1. 沒有兩個類似數字應鄰近彼此。例如：1223不允許，但允許2123。
2. 開始結束的數字不應該是一樣的。他們被認爲是循環相鄰。例如：2132是不允許的。
3. 如果輸入的長度是4位數，則結果排列的長度也應該是4位數。

我可以使用任何類型的memoization來解決這個問題嗎？我如何將它存儲在二維數組中？給小費謝謝！

Answer 1

由於您只對允許排列的數量感興趣，因此大多數輸入會導致相同的結果。

• 在輸入數字的順序並不重要
• 只有數字出現的頻率分佈是很重要的，即1123和1223導致了相同的答案。

分類的投入，根據數字頻率導致剛剛5種不同情況下的四位輸入：

class  examples 
4   4444, 2222, ... 
3 1  1211, 2232, ... 
2 2  1331, 4422, ... 
2 1 1  3413, 1123, ... 
1 1 1 1 1234, 4231, ... 

一旦你已經想通了，每個個案的答案，任何新的輸入可以處理得非常快。