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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Paint House III

Number: 1583

Difficulty: Hard

Paid? No

Companies: PayPal

Problem Description

Given m houses and n colors, each house must be painted (or may already be painted) with one of the n colors. When painting an unpainted house, you incur a given cost. A neighborhood is defined as a maximal contiguous group of houses with the same color. The goal is to paint the remaining uncolored houses such that exactly target neighborhoods are formed while minimizing the overall painting cost. If it is impossible to meet the requirement, return -1.

Key Insights

  • The challenge is solved using dynamic programming by keeping track of the house index, last painted color, and number of neighborhoods formed so far.
  • For each house, if it is already painted, the state updates without accumulating painting cost.
  • For an unpainted house, try each possible color and update the DP state while checking if a new neighborhood is created.
  • The DP recurrence carefully considers whether the current color is the same as the previous one (no new neighborhood) or different (thus increasing the neighborhood count).
  • Pruning is important: only consider states that do not exceed the target neighborhoods.

Space and Time Complexity

Time Complexity: O(m * n * target * n) where m is the number of houses and n is the number of colors.
Space Complexity: O(m * n * target) for the DP state storage.

Solution

This problem is solved using dynamic programming (DP). The DP array is defined as dp[i][j][k] representing the minimal cost to paint houses from 0 to i such that house i is painted with color j and k neighborhoods have been formed up to index i.
For a house that is already painted, the algorithm only updates the relevant state (with cost 0) and checks if a new neighborhood is created by comparing to the previous house color.
For a house that is not painted, it loops through all possible colors. If the current color is the same as the previous house, then the neighborhood count remains the same; if it is different, the neighborhood count increases by 1. The cost to paint is then added based on the provided cost matrix.
A high value is used to initialize the DP array to represent an unreachable state, and finally, the minimum cost satisfying exactly target neighborhoods is computed.

Code Solutions

# Python Solution for Paint House III
import sys

def minCost(houses, cost, m, n, target):
    # Use a large number to represent infinity
    INF = sys.maxsize
    
    # dp[i][c][k] is the minimum cost to paint up to house i,
    # where house i is painted with color c and we have formed k neighborhoods.
    # Note: using 1-indexed color for consistency.
    dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
    
    # Initialization for the first house
    if houses[0] != 0:
        # Already painted with given color (houses[0])
        color = houses[0]
        dp[0][color][1] = 0
    else:
        # House 0 is not painted, try every possible color.
        for color in range(1, n+1):
            dp[0][color][1] = cost[0][color-1]
    
    # Process houses from index 1 to m-1.
    for i in range(1, m):
        for curr_color in range(1, n+1):
            for k in range(1, target + 1):
                if dp[i-1][curr_color][k] == INF:
                    continue
                # If current house is already painted
                if houses[i] != 0:
                    new_color = houses[i]
                    new_k = k + (1 if new_color != curr_color else 0)
                    if new_k <= target:
                        dp[i][new_color][new_k] = min(dp[i][new_color][new_k], dp[i-1][curr_color][k])
                else:
                    # Try painting current house with every possible color candidate.
                    for new_color in range(1, n+1):
                        new_cost = dp[i-1][curr_color][k] + cost[i][new_color-1]
                        new_k = k + (1 if new_color != curr_color else 0)
                        if new_k <= target:
                            dp[i][new_color][new_k] = min(dp[i][new_color][new_k], new_cost)
    
    # The answer is the minimal cost for painting all houses with exactly target neighborhoods.
    ans = min(dp[m-1][color][target] for color in range(1, n+1))
    return -1 if ans == INF else ans

# Example usage:
houses = [0,0,0,0,0]
cost_matrix = [[1,10],[10,1],[10,1],[1,10],[5,1]]
print(minCost(houses, cost_matrix, 5, 2, 3))  # Expected output: 9
← Back to All Questions