Skip to main content

1473. Paint House III

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

Python​

Top Down DP​

  • 三維的DP...
from math import inf
from functools import cache


class Solution:
    def minCost(self, houses: List[int], costs: List[List[int]], m: int, n: int, target: int) -> int:
        @cache
        def dp(i: int, count: int, pre_color: int):
            if i == len(houses):
                return 0 if count == target else inf

            if count > target:
                return inf

            min_cost = inf

            if houses[i] != 0:
                # The house not yet paint
                new_count = count + (1 if houses[i] != pre_color else 0)
                return dp(i+1, new_count, houses[i])

            # The house is painted, go over all possible colors
            for color in range(1, n+1):
                new_count = count + (1 if color != pre_color else 0)
                min_cost = min(
                    min_cost,
                    costs[i][color-1] + dp(i+1, new_count, color)
                )

            return min_cost

        min_cost = dp(0, 0, 0)
        return min_cost if min_cost != inf else -1