Leetcode: 1473. Paint House III

Can we derive an invariant based on the smallest possible examples? If there is only one house, the answer is either 0 if it is painted or the cost of the cheapest color. If there are two house, you can increase the number of neighborhoods by painting the second house in a different color than the first house, or keep the same number of neighborhoods by painting it with the same color. Therefore, we can define the problem in terms of \(h\) the current house that you are painting, \(c\) the color that you want to use in this house and \(t\) the number of neighborhoods that you are allowed to create. Time and space complexity is \(O(n^2 \times m)\) where \(n\) is the number of houses and \(m\) is the number of colors.

from typing import List


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

        dp = [[[float("inf")] * C for _ in range(target + 1)] for _ in range(N)]
        left = [[float("inf")] * C for _ in range(target + 1)]
        right = [[float("inf")] * C for _ in range(target + 1)]
        for i in range(N - 1, -1, -1):
            if i == N - 1:
                if houses[i] == 0:
                    for c in range(C):
                        dp[i][1][c] = cost[i][c]
                else:
                    dp[i][1][houses[i] - 1] = 0
            else:
                for t in range(1, target + 1):
                    if houses[i] == 0:
                        for c in range(C):
                            dp[i][t][c] = cost[i][c] + min(
                                dp[i + 1][t][c], left[t - 1][c], right[t - 1][c]
                            )

                    else:
                        for c in range(C):
                            if c == houses[i] - 1:
                                dp[i][t][c] = min(
                                    dp[i + 1][t][c], left[t - 1][c], right[t - 1][c]
                                )

            for t in range(1, target + 1):
                for c in range(C):
                    left[t][c] = (
                        float("inf") if c == 0 else min(left[t][c - 1], dp[i][t][c - 1])
                    )
                for c in range(C - 1, -1, -1):
                    right[t][c] = (
                        float("inf")
                        if c == C - 1
                        else min(right[t][c + 1], dp[i][t][c + 1])
                    )

        ans = min(dp[0][target][c] for c in range(C))
        return -1 if ans == float("inf") else ans


assert (
    Solution().minCost(
        [0, 0, 0, 0, 0], [[1, 10], [10, 1], [10, 1], [1, 10], [5, 1]], 5, 2, 3
    )
    == 9
)
assert (
    Solution().minCost(
        [0, 2, 1, 2, 0], [[1, 10], [10, 1], [10, 1], [1, 10], [5, 1]], 5, 2, 3
    )
    == 11
)
assert (
    Solution().minCost(
        [3, 1, 2, 3], [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]], 4, 3, 3
    )
    == -1
)