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 IV

Difficulty: Medium

Problem Description

You are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cost of size n x 3, where cost[i][j] represents the cost of painting house i with color j + 1. The houses will look beautiful if they satisfy the following conditions:

  • No two adjacent houses are painted the same color.
  • Houses equidistant from the ends of the row are not painted the same color.

Return the minimum cost to paint the houses such that they look beautiful.

Key Insights

  • The problem requires a dynamic programming approach to track the minimum costs while adhering to the painting constraints.
  • We need to consider both the adjacent houses' colors and the colors of houses that are equidistant from the ends.
  • A recursive relation can be established to compute the minimum costs while ensuring no violations of the painting rules.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use dynamic programming. We will maintain a 2D array dp, where dp[i][j] represents the minimum cost to paint up to the i-th house with color j. We will iterate through each house and for each color, compute the minimum cost by considering the previous house's colors while making sure that no two adjacent houses have the same color.

We also need to ensure that the colors of houses equidistant from the ends do not match. This can be managed by tracking the colors used at mirrored positions.

Code Solutions

def minCost(cost):
    n = len(cost)
    dp = [[0] * 3 for _ in range(n)]
    
    # Initialize the first house's costs
    for j in range(3):
        dp[0][j] = cost[0][j]
    
    for i in range(1, n):
        for j in range(3):
            # Calculate the minimum cost for painting house i with color j
            dp[i][j] = cost[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3])
    
    # Handle the equidistant constraints
    min_cost = float('inf')
    for j in range(3):
        # Check the last house with different colors from the first
        if j == 0:
            min_cost = min(min_cost, dp[n-1][1] + cost[0][2], dp[n-1][2] + cost[0][1])
        elif j == 1:
            min_cost = min(min_cost, dp[n-1][0] + cost[0][2], dp[n-1][2] + cost[0][0])
        else:
            min_cost = min(min_cost, dp[n-1][0] + cost[0][1], dp[n-1][1] + cost[0][0])
    
    return min_cost
← Back to All Questions