題目連結：
題目意譯：
現在在一座小城市中有 m 間房子排成一列，每間房子需要被漆成 n 種顏色（編號為 1 到 n）其中的一種，而有些房子在去年夏天已經被漆過了，所以不應被再次漆牆。
一個「社區」定義為一些連續且顏色相同的房子所形成的盡可能大之群體。
例如說：house = [1,2,2,3,3,2,1,1] 包含著 5 個社區 [{1}, {2,2}, {3,3}, {2}, {1,1}]。
給定一個陣列 houses、一個大小為 m × n 的矩陣 cost 以及一整數 target，其中：
houses[i]：為房子 i 的顏色，而如果還沒被漆過牆則其值為 0。
cost[i][j]：為將房子 i 漆成顏色 j + 1 的成本。
回傳將剩餘所有房子都漆完的最小成本，使得這之中恰好有 target 個社區。如果這不可能完成，則回傳 -1。
限制：
m == houses.length == cost.length
n == cost[i].length
1 ≦ m ≦ 100
1 ≦ n ≦ 20
1 ≦ target ≦ m
0 ≦ houses[i] ≦ n
1 ≦ cost[i][j] ≦ 10 ^ 4
範例測資：
範例 1：
輸入： houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
輸出： 9
解釋： 把房子們以 [1,2,2,1,1] 這個方式去漆
該陣列包含 target = 3 社區，即 [{1}, {2,2}, {1,1}]。
為所有房子漆牆的成本 (1 + 1 + 1 + 1 + 5) = 9。
範例 2：
輸入： houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
輸出： 11
解釋： 有些房子已經被漆過了。把房子以 [2,2,1,2,2]這個方式去漆
該陣列包含 target = 3 社區，即 [{2,2}, {1}, {2,2}]。
為第一間以及最後一間房子漆牆的成本 (10 + 1) = 11。
範例 3：
輸入： houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
輸出： -1
解釋： 這些房子原本就漆完了，而且之中總計有 4 個社區 [{3},{1},{2},{3}]，而不是 target = 3 個。
解題思維：
定義一陣列 D，其中 D[i][j][k] 代表著在前一間房子顏色是 j 且現在有 k 個社區的情況下，漆完剩餘房子（房子 i ～ m - 1）的最小成本為何（當然最後社區數還是要剛好 target 個）；而如果不可能做到或是不符合條件，則其值為無限大。其中 j = 0 時代表前一間房子的顏色不重要（主要是給房子 0，因為它沒有「前一間」）。
接著我們可以直接利用這個陣列來遞迴求解，而中途遇到已經求過的情況（(i, j, k) 與先前重複了）則直接使用該陣列之值即可：
可以看到最後我們的解答是在 D[0][0][0]，所以我們可以從這邊出發。
當我們現在在 D[i][j][k]（以下以 X 代稱）時，如果：
i = m，則所有房子都看完了，因此接下來需要看社區數的條件有沒有達成。如果 k 剛好是 target，則 X 之值應為 0（因為沒有房子要漆了，所以沒有成本）；反之，則為無限大（因為條件錯誤）。
i < m 且 k > target，則此時社區數不可能再降下去，所以 X 之值也應為無限大。
i < m 且 k ≦ target 且 houses[i] ≠ 0，則代表房子 i 已經有自己的顏色了，因此先判斷 houses[i] 與 j 是不是同一種顏色。如果不是則我們需要將 k 之值 + 1（代表社區數 + 1）。接著我們需要遞迴求 D[i + 1][houses[i]][k] 之值，而這將是 X 之值。
i < m 且 k ≦ target 且 houses[i] = 0，則我們可以自由選擇要把房子 i 漆成什麼顏色。而由於我們不知道哪個顏色會導致成本最小，因此 n 種顏色每一種都求求看即可。因此我們需要遞迴求 D[i + 1][y][k] + costs[i][y - 1]，其中 y 為 n 種顏色中的一種且 k 之值可能會多加 1（當 y 不與 j 相同時即需要加 1，因為會多出一個社區）。然後取出這些結果中的最小值，即是 X 之值。
因此遞迴求解得到 D[0][0][0] 之值後，如果其值為無限大，則代表我們不可能達成條件，因此需要回傳 -1；反之，則此時其為所求最小成本，因此回傳該值即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
