2025-08-01：粉刷房子Ⅳ。用go语言，给定一个偶数个房屋排列在一条直线上，和一个大小为 n x 3 的二维数组 cost
2025-08-01：粉刷房子Ⅳ。用go语言，给定一个偶数个房屋排列在一条直线上，和一个大小为 n x 3 的二维数组 cost
2025-08-01：粉刷房子Ⅳ。用go语言，给定一个偶数个房屋排列在一条直线上，和一个大小为 n x 3 的二维数组 cost，其中 cost[i][j] 表示给第 i 个房屋涂第 j + 1 种颜色的花费。
房屋的涂色需要满足两个条件才算“美观”：
- 1. 相邻的房屋颜色不能相同。
- 2. 距离两端位置相同的房屋（例如，第 0 和第 n-1 个房屋，第 1 和第 n-2 个房屋，以此类推）颜色也不能相同。
请计算出符合这些条件的涂色方案中，涂色总花费最低的方案所对应的最低开销。
2 <= n <= 100000。
n 是偶数。
cost.length == n。
cost[i].length == 3。
0 <= cost[i][j] <= 100000。
输入： n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]。
输出： 9。
解释：
最佳涂色顺序为 [1, 2, 3, 2]，对应的成本为 [3, 2, 1, 3]。满足以下条件：
不存在涂成相同颜色的相邻房屋。
位置 0 和 3 的房屋（等距于两端）涂成不同的颜色 (1 != 2)。
位置 1 和 2 的房屋（等距于两端）涂成不同的颜色 (2 != 3)。
使房屋看起来漂亮的最低涂色成本为 3 + 2 + 1 + 3 = 9。
题目来自力扣3429。
解题思路
由于房屋是对称的，我们可以将房屋分成对称的两部分来处理。对于第 i 个房屋和第 n-1-i 个房屋，我们需要确保它们的颜色不同，同时相邻房屋的颜色也不同。
动态规划状态定义
我们可以使用动态规划来解决这个问题。定义 f[i][j][k] 表示处理到第 i 对对称房屋时，前一个房屋的颜色为 j，当前对称对中第一个房屋的颜色为 k 时的最小总花费。
状态转移
对于每一对对称的房屋（第 i 个和第 n-1-i 个），我们需要选择它们的颜色：
- 1. 第 i 个房屋的颜色不能与前一个房屋的颜色相同（相邻约束）。
- 2. 第 i 个房屋和第 n-1-i 个房屋的颜色不能相同（对称约束）。
- 3. 第 n-1-i 个房屋的颜色不能与下一个房屋的颜色相同（相邻约束，但下一个房屋的颜色尚未确定，因此需要在下一对处理时考虑）。
因此，对于每一对房屋，我们需要枚举前一个房屋的颜色和当前对称对中第一个房屋的颜色，然后选择满足约束的颜色组合，并更新动态规划状态。
初始化
初始时，没有前一个房屋，因此可以认为前一个房屋的颜色是“虚拟”的（即可以任意选择，但需要在后续处理中确保约束）。
结果计算
处理完所有对称对后，我们需要在所有可能的最后状态中选择最小的总花费。
具体步骤
- 1. 对称处理：将房屋分成对称的两部分，例如对于 n=4，第 0 和第 3 个房屋为一对，第 1 和第 2 个房屋为一对。
- 2. 动态规划填充：
- • 对于每一对房屋，枚举前一个房屋的颜色和当前对称对中第一个房屋的颜色。
- • 确保当前对称对中两个房屋的颜色不同。
- • 确保当前对称对中第一个房屋的颜色与前一个房屋的颜色不同。
- • 更新动态规划状态。
- 3. 结果提取：在动态规划表的最后一行中，找到最小的总花费。
时间复杂度和空间复杂度
- • 时间复杂度：对于每一对房屋，我们需要枚举前一个颜色和当前颜色，因此时间复杂度为 O(n * 3 * 3) = O(n)。因为 3 是颜色数量的常数。
- • 空间复杂度：动态规划表的大小为 O(n/2 * 3 * 3) = O(n)，因为我们需要存储每一对房屋的状态。
示例解释
对于输入 n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]：
- 1. 对称对为 (0, 3) 和 (1, 2)。
- 2. 对于 (0, 3)：
- • 选择颜色组合 (j, k) 满足 j != k。
- • 例如选择颜色 1 和 2，花费为 3 + 5 = 8。
- 3. 对于 (1, 2)：
- • 前一个颜色是 1 或 2（取决于 (0, 3) 的选择）。
- • 选择颜色组合满足不与前一个颜色相同，且两个颜色不同。
- • 例如如果前一个是 1，可以选择 (2, 3)，花费为 2 + 1 = 3。
- 4. 总花费为 8 + 3 = 11，但实际最优解是 9，说明需要更精细的状态转移。
实际最优解是：
- • (0, 3) 选择颜色 1 和 2，花费 3 + 5 = 8。
- • (1, 2) 选择颜色 2 和 3，花费 2 + 1 = 3。
- • 但相邻约束不满足（第 0 个颜色 1，第 1 个颜色 2；第 2 个颜色 3，第 3 个颜色 2）。
- • 更优解：
- • (0, 3) 选择颜色 1 和 2，花费 3 + 5 = 8。
- • (1, 2) 选择颜色 3 和 2，花费 9 + 1 = 10（不优）。
- • 或者：
- • (0, 3) 选择颜色 1 和 3，花费 3 + 7 = 10。
- • (1, 2) 选择颜色 2 和 1，花费 2 + 1 = 3。
- • 总花费 10 + 3 = 13。
- • 最优解是：
- • (0, 3) 选择颜色 1 和 2，花费 3 + 5 = 8。
- • (1, 2) 选择颜色 2 和 3，花费 2 + 1 = 3。
- • 但第 1 个和第 2 个颜色相同（2 和 2），违反对称约束。
- • 实际最优解：
- • (0) 颜色 1，花费 3。
- • (1) 颜色 2，花费 2。
- • (2) 颜色 3，花费 1。
- • (3) 颜色 2，花费 3。
- • 满足所有约束，总花费 3 + 2 + 1 + 3 = 9。
动态规划的优化
原始动态规划可能没有正确处理相邻约束和对称约束的结合。可能需要更精细的状态设计或优化。
Go完整代码如下：
.
package main
import (
"fmt"
"math"
"slices"
)
func minCost(n int, cost [][]int)int64 {
f := make([][3][3]int, n/2+1)
for i, row := range cost[:n/2] {
row2 := cost[n-1-i]
for preJ := range3 {
for preK := range3 {
res := math.MaxInt
for j, c1 := range row {
if j == preJ {
continue
}
for k, c2 := range row2 {
if k != preK && k != j {
res = min(res, f[i][j][k]+c1+c2)
}
}
}
f[i+1][preJ][preK] = res
}
}
}
// 枚举所有初始颜色，取最小值
res := math.MaxInt
for _, row := range f[n/2] {
res = min(res, slices.Min(row[:]))
}
returnint64(res)
}
func main() {
n := 4
cost := [][]int{{3, 5, 7}, {6, 2, 9}, {4, 8, 1}, {7, 3, 5}}
result := minCost(n, cost)
fmt.Println(result)
}
Python完整代码如下：
.
# -*-coding:utf-8-*-
import math
def min_cost(n, cost):
# f[i][j][k] 表示涂第i组（对称位置的两间房）时，
# 左边房屋颜色为 j，右边房屋颜色为 k 的最小花费
f = [[[math.inf]*3for _ in range(3)] for _ in range(n//2+1)]
# 初始化 f[0]，第一组前没有房屋，花费为0
for j in range(3):
for k in range(3):
f[0][j][k] = 0
for i in range(n//2):
row_left = cost[i]
row_right = cost[n - 1 - i]
for preJ in range(3):
for preK in range(3):
res = math.inf
for j, c1 in enumerate(row_left):
if j == preJ:
continue
for k, c2 in enumerate(row_right):
if k != preK and k != j:
cand = f[i][j][k] + c1 + c2
if cand < res:
res = cand
f[i+1][preJ][preK] = res
# 找出 f[n/2] 中的最小值
res = math.inf
for row in f[n//2]:
res = min(res, min(row))
return res
if __name__ == '__main__':
n = 4
cost = [
[3, 5, 7],
[6, 2, 9],
[4, 8, 1],
[7, 3, 5]
]
print(min_cost(n, cost))
腾讯云开发者
