class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
}
};
1473. 粉刷房子 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.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 10^4原站题解
javascript 解法, 执行用时: 160 ms, 内存消耗: 50.7 MB, 提交时间: 2023-06-15 14:24:35
/**
* @param {number[]} houses
* @param {number[][]} cost
* @param {number} m
* @param {number} n
* @param {number} target
* @return {number}
*/
var minCost = function(houses, cost, m, n, target) {
const INFTY = Number.MAX_VALUE;
// 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
for (let i = 0; i < m; ++i) {
--houses[i];
}
// dp 所有元素初始化为极大值
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0).map(() => new Array(target).fill(INFTY)));
const best = new Array(m).fill(0).map(() => new Array(target).fill(0).map(() => new Array(3).fill(INFTY)));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < target; ++j) {
// best[i][j][0] = best[i][j][2] = INFTY;
best[i][j][1] = -1;
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (houses[i] !== -1 && houses[i] !== j) {
continue;
}
for (let k = 0; k < target; ++k) {
if (i === 0) {
if (k === 0) {
dp[i][j][k] = 0;
}
} else {
dp[i][j][k] = dp[i - 1][j][k];
if (k > 0) {
// 使用 best(i-1,k-1) 直接得到 dp(i,j,k) 的值
const first = best[i - 1][k - 1][0];
const firstIdx = best[i - 1][k - 1][1];
const second = best[i - 1][k - 1][2];
dp[i][j][k] = Math.min(dp[i][j][k], (j === firstIdx ? second : first));
}
}
if (dp[i][j][k] !== INFTY && houses[i] === -1) {
dp[i][j][k] += cost[i][j];
}
// 用 dp(i,j,k) 更新 best(i,k)
const first = best[i][k][0];
const firstIdx = best[i][k][1];
const second = best[i][k][2];
if (dp[i][j][k] < first) {
best[i][k][2] = first;
best[i][k][0] = dp[i][j][k];
best[i][k][1] = j;
} else if (dp[i][j][k] < second) {
best[i][k][2] = dp[i][j][k];
}
}
}
}
let ans = INFTY;
for (let j = 0; j < n; ++j) {
ans = Math.min(ans, dp[m - 1][j][target - 1]);
}
return ans === INFTY ? -1 : ans;
};
java 解法, 执行用时: 16 ms, 内存消耗: 42.6 MB, 提交时间: 2023-06-15 14:24:04
class Solution {
// 极大值
// 选择 Integer.MAX_VALUE / 2 的原因是防止整数相加溢出
static final int INFTY = Integer.MAX_VALUE / 2;
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
// 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
for (int i = 0; i < m; ++i) {
--houses[i];
}
// dp 所有元素初始化为极大值
int[][][] dp = new int[m][n][target];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
Arrays.fill(dp[i][j], INFTY);
}
}
int[][][] best = new int[m][target][3];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < target; ++j) {
best[i][j][0] = best[i][j][2] = INFTY;
best[i][j][1] = -1;
}
}
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) {
if (i == 0) {
if (k == 0) {
dp[i][j][k] = 0;
}
} else {
dp[i][j][k] = dp[i - 1][j][k];
if (k > 0) {
// 使用 best(i-1,k-1) 直接得到 dp(i,j,k) 的值
int first = best[i - 1][k - 1][0];
int firstIdx = best[i - 1][k - 1][1];
int second = best[i - 1][k - 1][2];
dp[i][j][k] = Math.min(dp[i][j][k], (j == firstIdx ? second : first));
}
}
if (dp[i][j][k] != INFTY && houses[i] == -1) {
dp[i][j][k] += cost[i][j];
}
// 用 dp(i,j,k) 更新 best(i,k)
int first = best[i][k][0];
int firstIdx = best[i][k][1];
int second = best[i][k][2];
if (dp[i][j][k] < first) {
best[i][k][2] = first;
best[i][k][0] = dp[i][j][k];
best[i][k][1] = j;
} else if (dp[i][j][k] < second) {
best[i][k][2] = dp[i][j][k];
}
}
}
}
int ans = INFTY;
for (int j = 0; j < n; ++j) {
ans = Math.min(ans, dp[m - 1][j][target - 1]);
}
return ans == INFTY ? -1 : ans;
}
}
python3 解法, 执行用时: 668 ms, 内存消耗: 23 MB, 提交时间: 2023-06-15 14:23:48
class Entry:
def __init__(self):
self.first = float("inf")
self.first_idx = -1
self.second = float("inf")
class Solution:
def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
# 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
houses = [c - 1 for c in houses]
# dp 所有元素初始化为极大值
dp = [[[float("inf")] * target for _ in range(n)] for _ in range(m)]
best = [[Entry() for _ in range(target)] for _ in range(m)]
for i in range(m):
for j in range(n):
if houses[i] != -1 and houses[i] != j:
continue
for k in range(target):
if i == 0:
if k == 0:
dp[i][j][k] = 0
else:
dp[i][j][k] = dp[i - 1][j][k]
if k > 0:
# 使用 best(i-1,k-1) 直接得到 dp(i,j,k) 的值
info = best[i - 1][k - 1]
dp[i][j][k] = min(dp[i][j][k], (info.second if j == info.first_idx else info.first))
if dp[i][j][k] != float("inf") and houses[i] == -1:
dp[i][j][k] += cost[i][j]
# 用 dp(i,j,k) 更新 best(i,k)
info = best[i][k]
if dp[i][j][k] < info.first:
info.second = info.first
info.first = dp[i][j][k]
info.first_idx = j
elif dp[i][j][k] < info.second:
info.second = dp[i][j][k]
ans = min(dp[m - 1][j][target - 1] for j in range(n))
return -1 if ans == float("inf") else ans
golang 解法, 执行用时: 16 ms, 内存消耗: 6.9 MB, 提交时间: 2023-06-15 14:23:30
type entry struct {
first, firstIdx, second int
}
func minCost(houses []int, cost [][]int, m, n, target int) int {
const inf = math.MaxInt64 / 2 // 防止整数相加溢出
// 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
for i := range houses {
houses[i]--
}
// dp 所有元素初始化为极大值
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, target)
for k := range dp[i][j] {
dp[i][j][k] = inf
}
}
}
best := make([][]entry, m)
for i := range best {
best[i] = make([]entry, target)
for j := range best[i] {
best[i][j] = entry{inf, -1, inf}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if houses[i] != -1 && houses[i] != j {
continue
}
for k := 0; k < target; k++ {
if i == 0 {
if k == 0 {
dp[i][j][k] = 0
}
} else {
dp[i][j][k] = dp[i-1][j][k]
if k > 0 {
// 使用 best(i-1,k-1) 直接得到 dp(i,j,k) 的值
if b := best[i-1][k-1]; j == b.firstIdx {
dp[i][j][k] = min(dp[i][j][k], b.second)
} else {
dp[i][j][k] = min(dp[i][j][k], b.first)
}
}
}
if dp[i][j][k] != inf && houses[i] == -1 {
dp[i][j][k] += cost[i][j]
}
// 用 dp(i,j,k) 更新 best(i,k)
if b := &best[i][k]; dp[i][j][k] < b.first {
b.second = b.first
b.first = dp[i][j][k]
b.firstIdx = j
} else if dp[i][j][k] < b.second {
b.second = dp[i][j][k]
}
}
}
}
ans := inf
for _, res := range dp[m-1] {
ans = min(ans, res[target-1])
}
if ans == inf {
return -1
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
golang 解法, 执行用时: 36 ms, 内存消耗: 6.7 MB, 提交时间: 2023-06-15 14:23:01
func minCost(houses []int, cost [][]int, m, n, target int) int {
const inf = math.MaxInt64 / 2 // 防止整数相加溢出
// 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
for i := range houses {
houses[i]--
}
// dp 所有元素初始化为极大值
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, target)
for k := range dp[i][j] {
dp[i][j][k] = inf
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if houses[i] != -1 && houses[i] != j {
continue
}
for k := 0; k < target; k++ {
for j0 := 0; j0 < n; j0++ {
if j == j0 {
if i == 0 {
if k == 0 {
dp[i][j][k] = 0
}
} else {
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
}
} else if i > 0 && k > 0 {
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j0][k-1])
}
}
if dp[i][j][k] != inf && houses[i] == -1 {
dp[i][j][k] += cost[i][j]
}
}
}
}
ans := inf
for _, res := range dp[m-1] {
ans = min(ans, res[target-1])
}
if ans == inf {
return -1
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
python3 解法, 执行用时: 3032 ms, 内存消耗: 21 MB, 提交时间: 2023-06-15 14:22:38
class Solution:
def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
# 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
houses = [c - 1 for c in houses]
# dp 所有元素初始化为极大值
dp = [[[float("inf")] * target for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if houses[i] != -1 and houses[i] != j:
continue
for k in range(target):
for j0 in range(n):
if j == j0:
if i == 0:
if k == 0:
dp[i][j][k] = 0
else:
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k])
elif i > 0 and k > 0:
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1])
if dp[i][j][k] != float("inf") and houses[i] == -1:
dp[i][j][k] += cost[i][j]
ans = min(dp[m - 1][j][target - 1] for j in range(n))
return -1 if ans == float("inf") else ans
cpp 解法, 执行用时: 320 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-15 14:22:19
/**
* 动态规划
* 设 dp(i,j,k) 表示将 [0,i] 的房子都涂上颜色，最末尾的第 i 个房子的颜色为 j，
* 并且它属于第 k 个街区时，需要的最少花费。
**/
class Solution {
private:
// 极大值
// 选择 INT_MAX / 2 的原因是防止整数相加溢出
static constexpr int INFTY = INT_MAX / 2;
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
// 将颜色调整为从 0 开始编号，没有被涂色标记为 -1
for (int& c: houses) {
--c;
}
// dp 所有元素初始化为极大值
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(target, INFTY)));
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 j0 = 0; j0 < n; ++j0) {
if (j == j0) {
if (i == 0) {
if (k == 0) {
dp[i][j][k] = 0;
}
}
else {
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
}
}
else if (i > 0 && k > 0) {
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1]);
}
}
if (dp[i][j][k] != INFTY && houses[i] == -1) {
dp[i][j][k] += cost[i][j];
}
}
}
}
int ans = INFTY;
for (int j = 0; j < n; ++j) {
ans = min(ans, dp[m - 1][j][target - 1]);
}
return ans == INFTY ? -1 : ans;
}
};