粉刷房子 III

标签: 数组 动态规划

难度: Hard

在一个小城市里，有 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.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

Submission

运行时间: 72 ms

内存: 19.1 MB

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]
        if houses[0] == 0:
            for i in range(n):
                dp[0][0][i] = cost[0][i]
        else:
            dp[0][0][houses[0]-1] = 0
        for i in range(1,m):
            min_t = max(target-(m-i-1)-1,1)
            max_t = min(target,i+2)
            if houses[i] == 0:
                for t in range(min_t,max_t):
                    tmp = dp[i-1][t-1]
                    min_idx = -1
                    min_idx_ = -1
                    for j in range(n):
                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:
                            min_idx_ = min_idx
                            min_idx = j
                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:
                            min_idx_ = j
                    for j in range(n):
                        if j == min_idx:
                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]
                        else:
                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]
                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]
            else:
                j = houses[i]-1
                for t in range(min_t,max_t):
                    tmp = dp[i-1][t-1][:]
                    tmp[j] = dp[i-1][t][j]
                    dp[i][t][j] = min(tmp)
                dp[i][0][j] = dp[i-1][0][j]
        res = min(dp[-1][-1])
        if res >= 1e6+1:
            return -1
        return res

Explain

这个题解使用了动态规划的方法。状态定义为 dp[i][t][j]，表示前 i+1 个房子构成 t+1 个街区，且第 i 个房子颜色为 j+1 时的最小花费。初始状态处理第一个房子的颜色和花费。对于每个房子，如果未涂色，考虑涂不同颜色的花费；如果已涂色，则直接更新花费。计算时，保持两个最小值（min_idx 和 min_idx_），用于优化时间复杂度，避免重复计算。最后返回所有情况中的最小花费，如果不存在有效方案则返回 -1。

时间复杂度: O(m * target * n * n)

空间复杂度: O(m * target * n)

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        # 初始化动态规划数组，所有值设为一个极大数
        dp = [[[1e6+1]*n for j in range(target)] for i in range(m)]
        # 处理第一个房子的初始情况
        if houses[0] == 0:
            for i in range(n):
                dp[0][0][i] = cost[0][i]
        else:
            dp[0][0][houses[0]-1] = 0
        # 遍历每个房子
        for i in range(1,m):
            min_t = max(target-(m-i-1)-1,1)
            max_t = min(target,i+2)
            if houses[i] == 0:
                for t in range(min_t,max_t):
                    tmp = dp[i-1][t-1]
                    min_idx = -1
                    min_idx_ = -1
                    for j in range(n):
                        if min_idx == -1 or tmp[min_idx] >= tmp[j]:
                            min_idx_ = min_idx
                            min_idx = j
                        elif min_idx_ == -1 or tmp[min_idx_] >= tmp[j]:
                            min_idx_ = j
                    for j in range(n):
                        if j == min_idx:
                            dp[i][t][j] = min(tmp[min_idx_], dp[i-1][t][j]) + cost[i][j]
                        else:
                            dp[i][t][j] = min(tmp[min_idx], dp[i-1][t][j]) + cost[i][j]
                        dp[i][0][j] = dp[i-1][0][j] + cost[i][j]
            else:
                j = houses[i]-1
                for t in range(min_t,max_t):
                    tmp = dp[i-1][t-1][:]
                    tmp[j] = dp[i-1][t][j]
                    dp[i][t][j] = min(tmp)
                dp[i][0][j] = dp[i-1][0][j]
        res = min(dp[-1][-1])
        if res >= 1e6+1:
            return -1
        return res

Explore

在这个问题的上下文中，当`houses[0]`为0，意味着第一个房子尚未被涂色，因此需要从`cost`数组中选择一个颜色来涂色，并且支付相应的费用。而如果`houses[0]`不为0，表示第一个房子已经预先涂有一种颜色，这种情况下不需要再支付涂色费用，因此初始化花费为0。这种设定是基于只考虑额外的涂色费用，预设的颜色被视为无需额外费用的初始状态。

状态转移方程通过控制`target`个街区的形成来确保正确的街区数量。在动态规划中，`t`表示已形成的街区数量。当我们考虑第`i`个房子时，如果将其涂成与前一个房子不同的颜色，则街区数量增加（即`t+1`），并且在`dp[i][t][j]`的计算中使用`dp[i-1][t-1][j]`的值；如果颜色与前一个房子相同，则街区数量不变，使用`dp[i-1][t][j]`来更新。通过这种方式，算法确保最终形成的街区数量正好是`target`。

在代码中，`min_t`和`max_t`用于确定在处理第`i`个房子时可能的街区数的范围。`min_t`表示在考虑到剩余房子数量后能形成的最小街区数，它确保了即使每个后续房子都形成一个新的街区，也不会超过`target`个街区。`max_t`表示考虑到当前房子位置时能形成的最大街区数，它确保不会因为房子数量不足而无法形成足够的街区。这两个值的计算保证了动态规划在合理的街区数范围内进行，避免无效的计算。

在处理涂色成本时，使用`min_idx`和`min_idx_`是为了优化时间复杂度并减少冗余计算。`min_idx`存储当前最小花费的颜色索引，而`min_idx_`存储次小花费的颜色索引。这样，在更新当前房子的颜色成本时，如果当前房子选择的是最小花费颜色，则可以使用次小花费来计算新的成本；如果不是，则使用最小花费。这种方法有效避免了在每次更新时重新计算所有颜色的最小和次小成本，提高了效率。