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

动态规划 困难 每日一题

题目都没看完，果断cv

https://leetcode-cn.com/problems/paint-house-iii/comments/

👇或者记忆化递归

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:

        @lru_cache(None)
        def dfs(i, target, color):
            if target == 0 and i == m:
                return 0
            if target == -1 or i == m:
                return float("inf")

            if houses[i] != 0:
                return dfs(i+1, target if houses[i]==color else target-1, houses[i])
            else:
                return min(dfs(i+1, target if j+1==color else target-1, j+1) + cost[i][j] for j in range(n))

        ans = dfs(0, target, -1)
        return ans if ans != float("inf") else -1