在一個小城市里，有 m 個房子排成一排，你需要給每個房子涂上 n 種顏色之一（顏色編號為 1 到 n ）。有的房子去年夏天已經涂過顏色了，所以這些房子不需要被重新涂色。

我們將連續相同顏色盡可能多的房子稱為一個街區。（比方說 houses = [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 。

示例 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 = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
輸出：5
示例 4：

輸入：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 個街區。

解題思路

數組dp[i][j][k]中存儲的元素含義是前i座房子并且第i座房子的顏色是j并且街區數目為k時，產生的最小花費

代碼解讀

1.這段代碼作用是將房子的顏色從0開始編號，使得后面顏色的遍歷直接從0開始

        for (int i = 0; i < houses.length; i++) {houses[i]--;}

2.這段代碼作用是初始化dp數組，將全部元素置為最大值，因為題目需要選出的時最小值，因此沒有填入元素的位置即為最大值，后面在比較的時候就會失效

        for (int i = 0; i <m ; i++) {for(int j=0;j<n;j++)Arrays.fill(dp[i][j],max);}

3.狀態轉移

        for (int i = 0; i <m ; i++) {//遍歷所有房子for(int j=0;j<n;j++){//遍歷所有顏色if(houses[i]!=-1&&houses[i]!=j)  continue;
//條件等價于houses[i]==-1||houses[i]==j，就直接下一輪循環
//houses[i]==-1代表房子沒上色，houses[i]==j代表當前房子已經上色并且顏色是j，因為顏色已經固定了，所以
//dp[i][j][k]只能在j==houses[i]的情況下填入元素，顏色j等于其他值的情況是不可能出現for (int k = 0; k < target; k++) {//遍歷街區個數for (int p = 0; p < n; p++) {//遍歷前一個房子的顏色//先分為兩種情況 //情況一：前一個房子和當前房子同色//情況二：前一個房子和當前房子不同色   if (p==j)//情況一：前一個房子和當前房子同色{if(i==0)//1.當前房子是第一家，因此不能從前一座房子轉移狀態{if(k==0)//當前街區數只可能為0，因為當前只有一家房子，不可能產生k>0 dp[i][j][k]=0;}else{//2.當前房子不是第一家dp[i][j][k]= Math.min(dp[i][j][k],dp[i-1][j][k]);//因為前一個房子和當前房子同色，因此街區數是沒有增加的，顏色也是和前面房子的一樣}}else if(i>0&&k>0){//情況二：前一個房子和當前房子不同色dp[i][j][k]= Math.min(dp[i][j][k],dp[i-1][p][k-1]);//因為當前房子和前一個房子，顏色不一樣，因此需要產生一個新的街區}}if(houses[i]==-1&&dp[i][j][k]!=max)
//houses[i]==-1代表房子沒上色，dp[i][j][k]!=max 代表從前面的循環中是不能向dp[i][j][k]填入元素的
//例如 dp[0][j][k](k>1) 這種情況是不可能出現的，因此不能填入元素，也不能在計算這種情況的花費dp[i][j][k]+=cost[i][j];}}}

4.dp[m-1][i][target-1]，m-1代表所有房子（前m座房子），target-1代表有target個街區，i是最后一個房子的顏色，找出最小值。

        for (int i = 0; i < n; i++) {res= Math.min(res,dp[m-1][i][target-1]);}

代碼

class Solution {static int max=Integer.MAX_VALUE/2;public int minCost(int[] houses, int[][] cost, int m, int n, int target) {int[][][] dp=new int[m][n][target];for (int i = 0; i < houses.length; i++) {houses[i]--;}for (int i = 0; i <m ; i++) {for(int j=0;j<n;j++)Arrays.fill(dp[i][j],max);}for (int i = 0; i <m ; i++) {for(int j=0;j<n;j++){if(houses[i]!=-1&&houses[i]!=j)  continue;for (int k = 0; k < target; k++) {for (int p = 0; p < n; p++) {if (p==j){if(i==0){if(k==0)   dp[i][j][k]=0;}else{dp[i][j][k]= Math.min(dp[i][j][k],dp[i-1][j][k]);}}else if(i>0&&k>0){dp[i][j][k]= Math.min(dp[i][j][k],dp[i-1][p][k-1]);}}if(houses[i]==-1&&dp[i][j][k]!=max)dp[i][j][k]+=cost[i][j];}}}int res=max;for (int i = 0; i < n; i++) {res= Math.min(res,dp[m-1][i][target-1]);}return res==max?-1:res;}
}