主題
題目連結：
題目意譯：
你被給定兩整數 m 和 n。考慮一個大小為 m × n 的網格，而每一格一開始都是白的。你可以為每一格塗上紅、綠或是藍色。而所有格子都應被塗上顏色。
回傳為網格中所有格子塗上顏色並使得每兩個相鄰格子的顏色都不同的方法數。由於答案可能很大，先將其模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ m ≦ 5
1 ≦ n ≦ 1000
範例測資：
範例 1：
輸入： m = 1, n = 1
輸出： 3
解釋： 上圖顯示了三種可能的塗色方式。
範例 2：
輸入： m = 1, n = 2
輸出： 6
解釋： 上圖顯示了六種可能的塗色方式。
範例 3：
輸入： m = 5, n = 5
輸出： 580986
解題思維：
其實有點像這題的精神，就是窮舉即可（當然，要加上動態規劃（Dynamic Programming）的精神）。
由於 m 最大是 5，因此我們可以直接窮舉出在只考慮「這個維度」中塗色的方法數，即 3 ^ m 種方式。然後我們先過濾出那些相鄰格子顏色相同的塗色方式。
假設對於當前 m 值來說，這種合法方式有 C 個。因此我們知道只塗第一個（直）行的話會有 C 種方式。為這些方式編號為 0 ～ C - 1。
接著我們可以套用動態規劃的精神：
定義一個二維陣列 D，其中 D[i][j] 代表著在第 i 行（索引值從 0 開始數）用編號 j 的塗色方式填上顏色後，第 0 ～ i - 1 行有多少種合法（即相鄰格子不同色）之塗色方式。
可以看到遞迴式為：
D[0][j] = 1，其中 0 ≦ j < C；
（上式為遞迴停止條件）
D[i][j] = sum(D[i - 1][k])，其中 i > 0 、 sum() 代表著加總之操作，且編號 k 的塗色方式與編號 j 的方式兩相對齊後相鄰格子不同色（因為編號 k 是第 i - 1 行而編號 j 是第 i 行，兩行之間的格子也需要不同色）。
而最後所求即為 D[n - 1][0] + D[n - 1][1] + …… + D[n - 1][C - 1]。當然，記得每個運算都要模 10 ^ 9 + 7 以免溢位。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
