题目
题目链接
在一个小城市里，有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。
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
分析
- 具有重叠子问题特征,大眼一看就是动态规划题目.
- 假如动态规划做复杂度大概在 mnntarget <= 1002020100,复杂度合适
- 可能的坑点:cost存在int溢出的可能.cost可能为0,只有0才能被涂色
dp[i][j][k]代表考虑第i个房子时刷为j颜色组成k个街区时的最小花费
dp[i][j][k] = min(
dp[i][j][k],
dp[i - 1][j][k]+cost, 相同颜色
dp[i-1][枚举not j][k-1]+cost 不同颜色
)
提交代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution:
def minCost(self, houses, cost, m, n, target):
dp = [[[-1 for i in range(target + 1)] for j in range(n)] for k in range(m)]
# cost =
def getCost(color, idx):
if houses[idx] == color:
return 0
return cost[idx][color - 1]
for j in range(n):
if houses[0] == 0 or j + 1 == houses[0]:
dp[0][j][1] = getCost(j + 1, 0)
# dp[i][j][k] = min(dp[i - 1][j][k] + (cost[i - 1][j - 1]), dp[i - 1][notj][k - 1] + (cost[i - 1][j - 1]))
def update(now, pre, cost):
if pre == -1:
return now
if now == -1:
return pre + cost
return min(pre + cost, now)
for i in range(1, m):
for k in range(1, target + 1):
for j in range(n):
if houses[i] == 0 or j + 1 == houses[i]:
c = getCost(j + 1, i)
for pre in range(n):
if pre == j:
dp[i][j][k] = update(dp[i][j][k], dp[i - 1][j][k], c)
else:
dp[i][j][k] = update(dp[i][j][k], dp[i - 1][pre][k - 1], c)
# print(dp)
ans = -1
for i in range(n):
ans = update(ans, dp[m - 1][i][target], 0)
return ans
|