We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Paint House III

Difficulty: Hard

Problem Description

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again. A neighborhood is a maximal group of continuous houses that are painted with the same color. Given an array houses, an m x n matrix cost and an integer target, return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

Key Insights

  • We need to track the number of neighborhoods formed by the painted houses.
  • Dynamic programming can be used to minimize the cost while also ensuring the required number of neighborhoods.
  • We can represent the state with three parameters: the current house index, the current number of neighborhoods, and the last color used for painting.
  • The problem can be solved by exploring all possible colors for unpainted houses and using previously computed states to build the solution.

Space and Time Complexity

Time Complexity: O(m * n * target)
Space Complexity: O(m * target)

Solution

The solution employs dynamic programming to keep track of the minimum cost to paint houses while ensuring that the exact number of neighborhoods is maintained. We use a 3D array dp where dp[i][t][c] represents the minimum cost to paint up to the ith house, resulting in exactly t neighborhoods, with the last house painted color c. We initialize our dp array with infinity and update it based on the costs from the cost matrix and the previously calculated states.

Code Solutions

def minCost(houses, cost, m, n, target):
    # Initialize DP array with infinity
    dp = [[[float('inf')] * (n + 1) for _ in range(target + 1)] for _ in range(m + 1)]
    dp[0][0][0] = 0  # Base case: no houses, no cost

    for i in range(1, m + 1):
        for t in range(1, target + 1):
            for c in range(n + 1):
                if houses[i - 1] > 0:  # Already painted
                    color = houses[i - 1]
                    new_neigh = 1 if (i == 1 or houses[i - 2] != color) else 0
                    dp[i][t][color] = min(dp[i][t][color], dp[i - 1][t - new_neigh][color])
                    for prev_color in range(1, n + 1):
                        if prev_color != color:
                            dp[i][t][color] = min(dp[i][t][color], dp[i - 1][t][prev_color])
                else:  # Not painted
                    for color in range(1, n + 1):
                        cost_to_paint = cost[i - 1][color - 1]
                        new_neigh = 1 if (i == 1 or houses[i - 2] != color) else 0
                        dp[i][t][color] = min(dp[i][t][color], dp[i - 1][t - new_neigh][color] + cost_to_paint)
                        for prev_color in range(1, n + 1):
                            if prev_color != color:
                                dp[i][t][color] = min(dp[i][t][color], dp[i - 1][t][prev_color] + cost_to_paint)

    result = min(dp[m][target][color] for color in range(1, n + 1))
    return result if result < float('inf') else -1
← Back to All Questions