給一個 n，代表 (n , 3) 的二維串列，每個位置可以填入R、G、Y三色，而每個顏色不能相鄰(上下左右)相同，要求出一共有幾種填法。
這是我第二次做到要取餘的題目，代表方法數真的很大。
如果 n = 7，就會超時。
我左右一看，感覺到這只是個數學問題，可以代公式求解，不用真的計算。結果真的找到公式，代上去只用 一百多毫秒 就能通過測試。
在我心中，用公式解，就像拋棄電腦強大計算能力不用，背棄了用程式語言邏輯去解決問題的宗旨，跟作弊是沒兩樣的。
於是我還是老實地寫出一個合格的解法。
先看題目，第一層有12種組合。每一層的所有組合，都在這12種之內。
第二層有多少種組合，取決於第一層，也就是最後一層相鄰的那一層。
每種組合後面能接上的組合是固定的，只要找出來，就不必去費心再去搜尋下一層有甚麼可能。
所有A組合能接的下一層組合，都加上A組合的數目。n層的總和就是n層所有組合的加總。
不論是三種顏色還是四種顏色，寬三格還是四格，都可以套用這樣的邏輯去處理。
class Solution:
def numOfWays(self, n: int) -> int:
# 建立第一層
memo = dict()
memo["now"] = {}
memo["next"] = {}
colors = set(["r","g","y"])
# 找到所有顏色組合
def findColorSet(stats):
if len(stats) == 3:
memo["now"][stats] = 1
return
for c in colors:
if not stats or c != stats[-1]:
findColorSet(stats+c)
findColorSet("")
#
c2c = {}
for c1 in memo["now"]:
c2c[c1] = []
for c2 in memo["now"]:
isLegal = True
for ch1, ch2 in zip(c1,c2):
if ch1 == ch2:
isLegal = False
break
if isLegal:
c2c[c1].append(c2)
#
if n > 1:
keys = memo["now"].keys()
for row in range(2,n+1):
memo["next"] = {}.fromkeys(keys,0)
for key in keys:
v = memo["now"][key]
for key2 in c2c[key]:
memo["next"][key2] += v
memo["now"].update(memo["next"])
return sum(memo["now"].values()) % (10**9+7)
這樣子符合要求我自身要求，用程式邏輯找到答案。
下面附贈公式解，也是我第一個想出來的解法。
class Solution2:
def numOfWays(self, n: int) -> int:
self.ans = 0
table = dict()
table2 = dict()
table2[1] = 12
table[1] = 0
table2[2] = table2[1]*9//2+table[1]
table[2] = 3
if n >= 3:
for i in range(3, n+1):
table2[i] = table2[i-1]*9//2+table[i-1]
table[i] = table2[i-2]+table[i-1]
return table2[n] % (10**9+7)