一、题目

在一个小城市里，有 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 。

点击查看原题

二、思路

由于第i个房子粉刷成什么颜色，依赖于之前的房子刷的颜色进行计算，并且只依赖于前一个房子。明显是一个动态规划问题，即把之前粉刷的状态记录下来。
根据粉刷的颜色来判断街区，现在研究一下0~i房子颜色和0~i+1房子颜色对街区划分的影响，如下：

如果i+1个房子和i房子颜色相同，则街区划分不变 如果颜色不同，则街区数量+1

由上述推断可以得知，只需要关注前一块的颜色和街区数量，记录下该颜色和街区数量下花费的最小值即可。
定义动态规划数组dp[i][j][k]，其中i是指第i-1个房子，j是房子粉刷的第j-1种颜色，k-1指该房子颜色下的街区数量，值的含义是粉刷花费的最小值。可以得到下述的状态转移方程：(dp全部初始化为Integer.MAX_VALUE/2)。

1）当house[i] != 0时，已经有原来颜色，0 <= loc < cost[0].length： 1473. 粉刷房子 III-每日一题 - 图1 2）当house[i] == 0时，无原来颜色，0 <= loc,j < cost[0].length： 1473. 粉刷房子 III-每日一题 - 图2

第1）个是因为已经有原来颜色，不可以更改，所以其他颜色地方就都为Integer.MAX_VALUE/2，只有dp[i][house[i] - 1][k]可以更改。而2）是没有颜色，所有颜色都可以刷。

三、代码

  1. class Solution {
  2.     public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
  3.         // i第(几个-1)房子，j第(几个-1)颜色，k组成(几个-1)街区
  4.         int[][][] dp = new int[houses.length][cost[0].length][target];
  5.         for (int i = 0; i < dp.length; i++) {
  6.             for (int j = 0; j < dp[0].length; j++) {
  7.                 Arrays.fill(dp[i][j], Integer.MAX_VALUE / 2);
  8.             }
  9.         }
  10.         if (houses[0] == 0) {    // 第一个房子无颜色
  11.             for (int i = 0; i < cost[0].length; i++) {  // 初始化第一行
  12.                 dp[0][i][0] = cost[0][i];    // 由于只有一个房子，所以，数量也只能为1，也就是k=0
  13.             }
  14.         } else {    // 有颜色则无法更改，代价也应该为0
  15.             dp[0][houses[0] - 1][0] = 0;
  16.         }
  17.         for (int i = 1; i < houses.length; i++) {
  18.             for (int j = 0; j < cost[0].length; j++) {
  19.                 // 当房子原来有颜色，那么不可改变颜色，只能更新原有颜色与之前颜色的代价，其他颜色跳过
  20.                 if (houses[i] != 0 && houses[i] != j+1) {
  21.                     continue;
  22.                 }
  23.                 for (int k = 0; k < target; k++) {
  24.                     for (int loc = 0; loc < cost[0].length; loc++) {
  25.                         if (loc == j) {
  26.                             // 与前一个房子颜色相同，分块数量一样
  27.                             dp[i][j][k] = Math.min(dp[i][j][k], dp[i-1][loc][k]);
  28.                         } else if (k > 0) {
  29.                             // 与前一个颜色不同，分数数量增加了1
  30.                             dp[i][j][k] = Math.min(dp[i][j][k], dp[i-1][loc][k-1]);
  31.                         }
  32.                     }
  33.                     // 只有dp[i][j][k]有解且房子无原有颜色，才增加粉刷成本
  34.                     if (dp[i][j][k] != Integer.MAX_VALUE/2 && houses[i] == 0) {
  35.                         dp[i][j][k] += cost[i][j];
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         int ans = Integer.MAX_VALUE;
  41.         // 遍历，找到分块为target的最低代价
  42.         for (int j = 0; j < cost[0].length; j++) {
  43.             ans = Math.min(ans, dp[houses.length - 1][j][target - 1]);
  44.         }
  45.         return ans == Integer.MAX_VALUE / 2 ? -1 : ans;
  46.     }
  47. }

时间复杂度1473. 粉刷房子 III-每日一题 - 图3，空间复杂度1473. 粉刷房子 III-每日一题 - 图4。
由于当前解只依赖于上一个解，所以空间复杂度可以优化到1473. 粉刷房子 III-每日一题 - 图5，这里不做优化处理。
由于嵌套循环种的第四个循环，只找最小值即可，可以使用记忆化来记录，降低时间到1473. 粉刷房子 III-每日一题 - 图6。这里也不做优化。