题目大意：
给房子涂色 III
在一个小城市里，有 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 个街区。提示：
- 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1473
解题思路分析：
这种题目我们很难一眼看出答案，必须尝试每一种组合方式来找到一个最优解。对于这种问题最高效的方式就是使用动态规划DP，来遍历每一种情况，进而从中找到最优方案。对于DP问题我更习惯使用递归加记忆数组的方式，本题我们也会采用递归方式来做讲解。
- 建立递归方法，定义三个方法参数，分别是当前房屋下标index，尚未分组个数target，相邻前一个房子的颜色lastColor。
- 递归中，如果target小于0，返回-1。如果index等于房屋数量，证明已递归完所有房屋，此时查看target是否正好等于0，如果不是，说明没有将所有房屋分为target个街区，返回-1，反之返回0。
- 如果当前房屋已经存在颜色（houses[index]>0），我们无须再上色，因此也不会产生cost。这时需要判断当前颜色是否与前一栋房子颜色lastColor相同，如果相同，代表他们是同一街区，即target不变。反之，说明当前房屋不属于上一个街区，换句话说它是一个新街区的起点，此时target减一。另外将index加一，并将当前房屋颜色作为lastColor传入递归函数（递归至下一栋房屋），返回结果即是当前递归的返回结果。
- 如果当前房屋没有颜色（houses[index]==0），那么我们就需要在所有颜色中选择一种为他涂色，因为我们无法得知选择哪一种颜色能使得全局花费最小，因此需要尝试每一种选择，所有选择中总花费最小的即是当前返回结果。我们循环每一种颜色，首先查看当前颜色是否等于前一栋房子颜色lastColor，如果相同target不变。反之target-1。另外将index加一，并将当前房屋颜色作为lastColor传入递归函数（递归至下一栋房屋）。如果递归函数的返回值是-1，代表当前选择无法产生一个合理解，跳过，继续循环到下一种颜色。如果递归函数能够返回一个合理解，那么再加上当前涂色的费用，这既是一个合理解，用该合理解更新当前递归的最小值。循环完所有颜色后，最小值即是本层递归的返回值。
- 上述递归实际上是暴力枚举每一种涂色方式，然后通过局部最优一步一步推出全局最优。对于暴力枚举，必将会产生大量重复计算，因此我们需要使用一个记忆数组来记录已经计算过的数值，避免重复计算从而提高效率。递归函数中存在3个变量，所以我们需要建立一个三维数组来记录递归函数的返回值（具体参照代码）。
实现代码：
Integer[][][] memo; // 记忆数组
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
memo=new Integer[m][target+1][n+1]; // 初始化记忆数组
return help(houses,cost,0,target,0); // 递归求解
}
int help(int[] houses, int[][] cost, int index, int target, int lastColor){
if(target<0) return -1; // 如果target小于0，返回-1。
// 递归完所有下标后，若target正好等于0，返回0，反之返回-1
if(index==houses.length) return target==0?0:-1;
// 如果记忆数组中存在当前解，直接返回
if(memo[index][target][lastColor]!=null) return memo[index][target][lastColor];
// 当前房屋已经上色
if(houses[index]>0){
// 当前颜色
int color=houses[index];
// 如果与上一间房屋颜色不同，开启新街区，target减一
if(color!=lastColor)target--;
// 递归至下一房屋
return help(houses,cost,index+1,target,color);
}
// 最小化费
int min=Integer.MAX_VALUE;
// 循环每一种颜色
for(int c=1;c<=cost[0].length;c++){
// 递归至下一件房屋
int costTemp=help(houses,cost,index+1,c==lastColor?target:target-1,c);
// 递归函数如果返回-1，代表选择当前颜色不会产生合理解，跳过
if(costTemp==-1) continue;
// 递归函数结果加上当前花费
costTemp+=cost[index][c-1];
// 更新全局最小化费
min=Math.min(min,costTemp);
}
// 如果没找到合理解，min设置为-1
if(min==Integer.MAX_VALUE) min=-1;
// 将结果保存至记忆数组
memo[index][target][lastColor]=min;
return min;
}本题解法执行时间为40ms。
Runtime: 40 ms, faster than 30.05% of Java online submissions for Paint House III.
Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Paint House III.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1473-paint-house-iii-解题思路分析/