## [1473\. 給房子涂色 III](https://leetcode-cn.com/problems/paint-house-iii/) #### 思路 根據Hard必死定律，再加上周賽dp必死定律。這道題依舊是沒有做出來。但是這次做完了閱讀理解，也嘗試著在紙上構造了一下轉態轉移，也算是小有進步吧。 閱讀大佬解法，獲得新思路： * 動態規劃我們首先要找出狀態，狀態之前滿足**最優子問題**和**后無效性**，確定狀態轉移方程，然后開始求解 * 這道題中，分析狀態，主要有三個：`房子`、`顏色`、`街區` * 構造dp數組 `dp[k][i][j]` 代表涂到第k個房子，使用顏色i，街區數量為j時的最小花費 * 遍歷房子進行涂色，當前房子涂成什么顏色，是根據前邊的房子來的。所以將涂到第幾個房子作為第一維度。 * 假設0個房子有顏色1，`dp[0][1][1] = 0; dp[0][other][1] = math.inf` ，表示第0個房子已經涂了顏色了，不需要再涂，所以花費為0。其他的顏色無法再涂，花費為無窮大 * 假設一個房子的最小花費是無窮大，表示不可行，那也無法從這個房子進行狀態轉移 * **狀態轉移** ``` 1.當前房子有顏色 1.dp[k][i][j] = dp[k-1][i][j] （顏色相同，街區不加，且當前房子有顏色費用為0） 2.dp[k][i][j+1] = dp[k-1][!=i][j] （顏色不同，街區加1，當前房子有顏色，不用刷，當前費用為0） 2.當前房子沒有顏色 1.dp[k][i][j] = dp[k-1][i][j] + cost[k][i] （顏色相同，街區不加，加上刷當前的房子的費用） 2.dp[k][i][j+1] = dp[k-1][!=i][j] + cost[k][i]（顏色不同，街區加1，加上刷當前的房子的費用） ``` 以上，嘗試寫一下代碼。 #### 代碼 python3 ``` class Solution: def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int: dp = [[[math.inf for _ in range(m+1)] for _ in range(n+1)] for _ in range(m)] if houses[0] != 0: dp[0][houses[0]][1] = 0 else: for i in range(1,n+1): dp[0][i][1] = cost[0][i-1] for k in range(1, m): for pc in range(1,n+1): #前一個房間的顏色 for j in range(1,m): if dp[k-1][pc][j] == math.inf: #已經無效，無法進行狀態轉移 continue if houses[k] != 0: #當前房子已經涂過顏色 if houses[k] == pc: #當前房子和前一個顏色相同，分組不加 dp[k][houses[k]][j] = min(dp[k][houses[k]][j], dp[k-1][pc][j]) else: #不同顏色分組加1 dp[k][houses[k]][j+1] = min(dp[k][houses[k]][j+1], dp[k-1][pc][j]) else: for c in range(1,n+1): #當前房子未涂過顏色，可以涂任意的顏色 if c == pc: #當前顏色，不等于前一個顏色，分組不加 dp[k][c][j] = min(dp[k][c][j], dp[k-1][pc][j] + cost[k][c-1]) else: #不同顏色，分組加1 dp[k][c][j+1] = min(dp[k][c][j+1], dp[k-1][pc][j] + cost[k][c-1]) r = math.inf for i in range(1, n+1): r = min(r, dp[m-1][i][target]) return -1 if r == math.inf else r ```