愉快的五四青年节从遇到一道Hard的动态规划题结束~
题目链接：1473. 粉刷房子 III - 力扣（LeetCode） (leetcode-cn.com)
题目
在一个小城市里，有 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。
数据范围
m == houses.length == cost.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 10^4
分析
又是一道全无思路的题目。
显然本题需要使用动态规划，查看提示，建议我们使用一个三维数组 dp[i][j][k] ，其中 i 表示当前房子的下标， j 表示当前房子应该上的颜色， k 表示算上当前的房子一共有多少街区。 dp[i][j][k] 表示所需的最少花费。
我们与参考文章 [1] 使用相同的办法来对这些下标进行表示：
- 房屋编号从
0 ~ m - 1 - 颜色编号从
0 ~ n - 1 - 街区编号从
0 ~ target - 1 - 对应颜色编号，
houses数组的值全部 减一 ，则 使用-1来表示原本没有上色的房子 。
已经给定了这些数据和下标的含义之后，再来进行思考就比较简单了。使用本文的代码来进行分析，对于下标 idx 的房子以及它被刷上的颜色 color 和现在已有的街区数 district ，我们发现 dp[idx][color][district] 的数值应该取决于当前房屋 和上一间房屋 的颜色，假如：
- 当前房屋的颜色和上一间房屋的颜色
j0相同，街区数量不会变化，则dp[idx][color][district] == dp[idx - 1][color][district]； - 当前房屋颜色和上一间房屋的颜色
j0不同，街区数量应该加一，则dp[idx][color][district] == dp[idx - 1][j0][district - 1]；
当然，房子原本的颜色也会影响 dp 值的变化，具体实际上只有两方面：
- 房子原本没有颜色，即按照上面的规则
houses[idx] == -1，那么上面得到的dp值全都要加上cost[idx][color]； - 房子原本有颜色，如果此颜色与
color不同，那么这种上色方案无论如何是不可行的；如果此颜色与color相同，那么dp值就是我们上面分析的情况。
把这些分析加以实现，我们应该：
- 枚举房子下标 --> idx: 0 ~ m - 1
- 枚举上色方案 --> color: 0 ~ n - 1
- 如果房子有颜色且不同于 color，继续枚举颜色
- 运行至此有两种情况：房子没有颜色，或房子有颜色且颜色就是 color
- 如果房子下标 idx 是 0， 意味着没有上一个房子，dp[idx][color][0] = houses[idx] == -1 ? cost[0][color] : 0;继续枚举颜色
- 否则开始枚举街区 --> district: 0 ~ target - 1
- 枚举上一间房子的颜色 --> j0: 0 ~ n - 1
- 如果上一间房子的颜色和现在的颜色相同，设置 dp 值 // [1]
- 如果上一间房子的颜色和现在的颜色不同，设置 dp 值 // [2]
- 如果房子原本没有颜色，得到的 dp[idx][color][district] 要加上 cost[idx][color]
根据上面的实现来写代码，应该要注意几个要点：
- 在伪代码 [1] 和 [2] 处，由于我们在进行上一间房子颜色的枚举，不能简单地设置
dp[idx][color][district] == dp[idx - 1][j0][district]，而是应该根据dp的定义，取其中的最小值，即AC代码中所做的取min。 - 由于我们枚举的街区
district从0开始，对于当前房屋和上一间房屋颜色不同的情况，需要判断街区数大于0才有意义。 - 注意
cost[idx]添加的位置，枚举完上一间房子的颜色之后就进行添加，因为对于所有的district都要考虑这一情况。 - 我们如何表示
dp的初始值：由于随时可能在一个未被修改的dp上加上我们的cost，那么它的初始值就不能设置得太大，在具体实现中，我们重新定义了一下INT_MAX。
AC代码
class Solution {
public:
#undef INT_MAX
#define INT_MAX 0x3f3f3f3f
// #define DEBUG
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
int idx, color, district;
vector<vector<vector<int>>>
dp(m, vector<vector<int>>(n, vector<int>(target, INT_MAX)));
for (int& hc : houses)
{
hc--;
}
for (idx = 0; idx < m; idx++)
{
for (color = 0; color < n; color++)
{
// this color can not be applied
if (houses[idx] != -1 && houses[idx] != color)
continue;
if (idx == 0)
{
dp[idx][color][0] = houses[idx] == -1 ? cost[0][color] : 0;
continue;
}
// enum districts
for (district = 0; district < target; district++)
{
// enum the color of house[idx - 1] !!
for (int j0 = 0; j0 < n; j0++)
{
// same color
if (j0 == color)
{
// the district will not change
dp[idx][color][district] =
min(dp[idx][color][district], dp[idx - 1][j0][district]);
}
else
{
if (district)
dp[idx][color][district] =
min(dp[idx][color][district], dp[idx - 1][j0][district - 1]);
}
}
if (houses[idx] == -1)
{
dp[idx][color][district] += cost[idx][color];
}
}
}
}
# ifdef DEBUG
for (idx = 0; idx < m; idx++)
{
cout << "House " << idx << endl;
for (color = 0; color < n; color++)
{
cout << '\t' << "Color " << color << endl;
for (district = 0; district < target; district++)
{
cout << "\t\t" << dp[idx][color][district] << " ";
}
cout << endl;
}
}
#endif
int ans = INT_MAX;
for (color = 0; color < n; color++)
{
ans = min(ans, dp[m - 1][color][target - 1]);
}
if (ans == INT_MAX)
return -1;
else
return ans;
}
};
参考文章
[1] 力扣官方题解.粉刷房子 III[EB/OL].2021-05-02
[2] 宫水三叶.【宫水三叶】三维动态规划，以及其「状态定义」由来[EB/OL].2020-05-04