算法第七天-粉刷房子Ⅲ

粉刷房子Ⅲ

题目要求

解题思路

来自[宫水三叶]

动态规划

定义 f[i][j][k] 为开了前i间房子，且第 i 间房子的颜色编号为 j， 前 i 间房子形成的分区数量为 k 的所有方案中的[最小上色成本]。
我们不失一般性的考虑 f[i][j][k] 该如何转移，由于某些房子本身就已经上色了，上色的房子是不允许被粉刷的。
我们可以根据第 i 间房子是否已经被上色，进行分类情况讨论：

• 第i间房子已经被上色，即houses[i] != 0，此时只有满足 j==houses[i] 的状态才是有意义的，其余状态均为INF。
  同时根据[第i间房子的颜色j] 与 [第 i-1间房子的颜色p]是否相同，会决定第 i 间房子是否形成一个新的分区。这同样需要进行分情况讨论。
  整理后的状态转移方程为：
  $$\begin{array}{c}f[i][j][k]=\{\begin{array}{lc}min(f[i?1][j][k],f[i?1][p][k?1])& j==house[i],p!=j\\ INF& j!=house[i]\end{array}\end{array}\text{\hspace{1em}?}$$
• 第i间房子尚未被上色，即houses[i] == 0，此时房子可以被粉刷成任意颜色。不会有无效状态的情况。
  同样，根据[第i间房子的颜色j] 与 [第 i-1 间房子的颜色p]是否相同，会决定第i间房子是否形成一个新的分区。
  转移方程为：
  $$f[i][j][k]=min(f[i?1][j][k],f[i?1][p][k?1])+cost[i][j?1],p!=j$$
  一些编码细节：
• 下标转换：这是个人习惯，无论做什么题，都可以将下标转换成从1开始，目的是为了[节省负值下标的分情况讨论]、[将无效状态限制在0下标内]或者 [充当哨兵]
• 将0x3f3f3f3f 作为INF：因为目标是求最小值，我们应当使用一个较大值充当正无穷，来关联无效状态。同时为了确保不会出现[在正无穷基础上累加导致丢失正无穷含义]的歧义情况，我们可以使用有[累加空间]的值作为[正无穷]

代码

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        @functools.lru_cache(None)
        def dfs(i, j, blocks) :
            ret = 2147483647
            if blocks<=0 : return ret
            if i==0 : 
                return ret if blocks>1 else 0
            if houses[i-1]==0 :
                for k in range(1, n+1) :
                    ret = min(ret, dfs(i-1, k, blocks-int(j!=k))+cost[i-1][k-1])
                return ret
            ret = min(ret, dfs(i-1, houses[i-1], blocks-int(j!=houses[i-1])))
            return ret
        ans = 2147483647
        if houses[-1]==0 :
            for k in range(1, n+1) :
                ans = min(ans, dfs(m-1, k, target)+cost[m-1][k-1])
        else :
            ans = min(ans, dfs(m-1, houses[-1], target))
        return -1 if ans==2147483647 else ans

复杂度分析

时间复杂度：一共有$m?n?t$个状态需要被转移，每次转移需要枚举[所依赖的状态]的颜色，复杂度为$O(n)$。整体复杂度为$O(m?n^2?t)$
空间复杂度：$O(m?n?t)$