DP(18)：粉刷房子系列问题
Author：zhoulujun Date：
粉刷房子总共有三题
- 265. 粉刷房子 II（困难）：与I相似，但是颜色数量扩展到k种（ n x k 的矩阵 costs）。
- 1473. 粉刷房子 III（困难）：定一个 n x k 的矩阵 costs，表示每个房子需要粉刷 k 种颜色的成本，还有一个非负整数 target 表示你有多少钱，求粉刷前 n 个房子使得恰好有 target 个房子涂成相同颜色的最低成本。
粉刷房子
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1：输入: costs = [[17,2,17],[16,16,5],[14,3,19]] 输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。最少花费: 2 + 5 + 3 = 10。
剑指Offer给的答案还是看不懂：https://acoier.com/2023/11/03/剑指%20Offer%20II%20091.%20粉刷房子（中等）/
class Solution {
public int minCost(int[][] costs) {
int r = 0, g = 0, b = 0;
for (int[] cost : costs) {
int _r = r, _g = g, _b = b;
r = Math.min(_g, _b) + cost[0];
g = Math.min(_r, _b) + cost[1];
b = Math.min(_r, _g) + cost[2];
}
return Math.min(r, Math.min(g, b));
}
}动态规划解法：
你要用红/蓝/绿三种不同的颜色去粉刷 n 个房子，一个房子只能刷成一种颜色，并且相邻的房子不能粉刷相同的颜色。
动态分析
找到 “状态” 和 选择：
状态：初始 d(0, 0) = a(0, 0)、d(0, 1) = a(0, 1) 、d(0, 2) = a(0, 2)
选择：选择粉刷费用最小的，相邻的房子不能粉刷相同的颜色。
j 的取值只有 0/1/2 三种， 分别表示红/蓝/绿 3种颜色。
d(i,0) = min(d(i-1, 1), d(i-1, 2)) + a(i, 0)
d(i,1) = min(d(i-1, 0), d(i-1, 2)) + a(i, 1)
d(i,2) = min(d(i-1, 0), d(i-1, 1)) + a(i, 2)
dp 数组定义：
d(i,j) 表示粉刷 0~i号房子，并且第 i号房子使用第 j 种颜色的最小费用。
状态之间的关系：
public class LeetCode_256 {
// Time: O(n), Space: O(n)
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length;
int[][] d = new int[n][3];
d[0][0] = costs[0][0];
d[0][1] = costs[0][1];
d[0][2] = costs[0][2];
for (int i = 1; i < n; ++i) {
d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + costs[i][0];
d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + costs[i][1];
d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + costs[i][2];
}
return min(d[n-1][0], d[n-1][1], d[n-1][2]);
}
private int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}优化一：统一初始计算到循环中
d(i, j) 新定义： 表示粉刷 0~i-1 号房子，并且第 i-1 号房子使用第 j 种颜色的最小费用。
public class LeetCode_256 {
// Time: O(n), Space: O(n)
public int minCostOpt(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length;
int[][] d = new int[n+1][3];
for (int i = 1; i <= n; ++i) {
d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + costs[i-1][0];
d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + costs[i-1][1];
d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + costs[i-1][2];
}
return min(d[n][0], d[n][1], d[n][2]);
}
}优化二：空间复杂度优化到常量
public class LeetCode_256 {
// Time: O(n), Space: O(1)
public int minCostO1(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length;
int preR = 0, preB = 0, preG = 0;
for (int i = 1; i <= n; ++i) {
int curR = Math.min(preB, preG) + costs[i-1][0];
int curB = Math.min(preR, preG) + costs[i-1][1];
int curG = Math.min(preR, preB) + costs[i-1][2];
preR = curR;
preB = curB;
preG = curG;
}
return min(preR, preB, preG);
}
}粉刷房子 II（K 种颜色粉刷房子）
假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。
请你计算出粉刷完所有房子最少的花费成本。
示例：输入: [[1,5,3],[2,9,4]] 输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.
动态规划解法：
找到 “状态” 和 选择：
选择：选择粉刷费用最小的，相邻的房子不能粉刷相同的颜色。
dp数组定义：d(i, j)表示粉刷0~i-1号房子，并且第i-1号房子使用第j种颜色的最小费用。状态之间的关系：
d(i,j) = min(d(i-1, c)) + a(i-1, j)c: 0 -> k-1, c != ji: 1 -> nj: 0 -> k-1最后结果求：
min(d(n, i)), i: 0 -> k-1
public class LeetCode_265 {
// Time: O(n*k^2), Space: O(n*k)
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
if (k == 1) return costs[0][0];
int[][] d = new int[n + 1][k];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < k; ++j) {
int min = Integer.MAX_VALUE;
for (int c = 0; c < k; ++c) {
if (c != j) min = Math.min(min, d[i - 1][c]);
}
d[i][j] = min + costs[i - 1][j];
}
}
int min = d[n][0];
for (int i = 1; i < k; ++i) {
min = Math.min(min, d[n][i]);
}
return min;
}
}优化一：
public class LeetCode_265 {
// Time: O(n*k), Space: O(n*k)
public int minCostOpt(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
if (k == 1) return costs[0][0];
int[][] d = new int[n + 1][k];
int preIdx1 = 0, preIdx2 = 1;
for (int i = 1; i <= n; ++i) {
int idx1 = -1, idx2 = -1;
for (int j = 0; j < k; ++j) {
if (j != preIdx1) d[i][j] = d[i - 1][preIdx1] + costs[i - 1][j];
else d[i][j] = d[i - 1][preIdx2] + costs[i - 1][j];
if (idx1 < 0 || d[i][j] < d[i][idx1]) {
idx2 = idx1;
idx1 = j;
} else if (idx2 < 0 || d[i][j] < d[i][idx2]) {
idx2 = j;
}
}
preIdx1 = idx1;
preIdx2 = idx2;
}
int min = d[n][0];
for (int i = 1; i < k; ++i) {
min = Math.min(min, d[n][i]);
}
return min;
}
}优化三：空间复杂度优化到常量
public class LeetCode_265 {
// Time: O(n*k), Space: O(1)
public int minCostO1(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
if (k == 1) return costs[0][0];
int preMin1 = 0, preMin2 = 0;
int preIdx1 = 0;
for (int i = 1; i <= n; ++i) {
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
int idx1 = -1;
for (int j = 0; j < k; ++j) {
int cost;
if (j != preIdx1) cost = preMin1 + costs[i - 1][j];
else cost = preMin2 + costs[i - 1][j];
if (cost < min1) {
min2 = min1;
min1 = cost;
idx1 = j;
} else if (cost < min2) {
min2 = cost;
}
}
preMin1 = min1;
preMin2 = min2;
preIdx1 = idx1;
}
return preMin1;
}
}粉刷房子 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。
这是一个稍微复杂的变体，需要在动态规划的基础上引入一个维度来表示相同颜色的房子个数。
解析已经非常清晰了，没有必要讲了
参考文章：
【动态规划】粉刷房子问题 https://juejin.cn/post/7136214969720242183
转载本站文章《DP(18)：粉刷房子系列问题》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9161.html