Solution Explanation: Paint House III

This problem asks for the minimum cost to paint a row of houses with n color options, subject to constraints on the number of contiguous blocks of the same color (target) and pre-existing paint (houses). A dynamic programming approach is highly effective here.

Approach: 3D Dynamic Programming

The core idea is to build a 3D DP table f[i][j][k], where:

• i: Represents the house index (0 to m-1).
• j: Represents the color of the house at index i (1 to n).
• k: Represents the number of neighborhoods (contiguous blocks of the same color) formed so far (1 to target).

f[i][j][k] stores the minimum cost to paint houses 0 to i such that the last house (i) is painted color j, and there are k neighborhoods.

State Transition

We iterate through houses. For each house i:

1. Unpainted House (houses[i] == 0): We can choose any color j. The cost depends on the previous house's color (j0):

   • If j == j0, the number of neighborhoods remains the same (k). The cost is f[i-1][j0][k] + cost[i][j-1].
   • If j != j0, a new neighborhood starts, increasing the count to k. The cost is f[i-1][j0][k-1] + cost[i][j-1].

   We take the minimum cost over all possible j0.

2. Painted House (houses[i] != 0): The color j is fixed to houses[i]. We iterate through previous house colors j0:

   • If j == j0, the neighborhood count remains k. Cost is f[i-1][j0][k].
   • If j != j0, a new neighborhood starts. Cost is f[i-1][j0][k-1].

   Again, we take the minimum over all j0.

Base Case

For i = 0:

• If houses[0] == 0, f[0][j][1] = cost[0][j-1] for all colors j.
• If houses[0] != 0, f[0][houses[0]][1] = 0. (House is already painted).

Final Result

The final answer is the minimum of f[m-1][j][target] for all colors j, representing the minimum cost to paint all houses with target neighborhoods. If this minimum is still infinity, it means no solution exists, so we return -1.

Time and Space Complexity

• Time Complexity: O(m * n^2 * target). The three nested loops iterate through houses, colors, and neighborhood counts.
• Space Complexity: O(m * n * target). This is the size of the DP table.

Code Implementation (Python)

import sys
 
def minCost(houses, cost, m, n, target):
    inf = sys.maxsize
    dp = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
 
    # Base Case
    if houses[0] == 0:
        for j in range(1, n + 1):
            dp[0][j][1] = cost[0][j - 1]
    else:
        dp[0][houses[0]][1] = 0
 
    # DP Transition
    for i in range(1, m):
        for j in range(1, n + 1):
            for k in range(1, min(target + 1, i + 2)):  #k <= i+1 because at most i+1 neighborhoods are possible
                for j0 in range(1, n + 1):
                    if houses[i] == 0:
                        new_cost = cost[i][j - 1]
                    else:
                        new_cost = 0 if houses[i] == j else inf
 
                    if j == j0:
                        dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k] + new_cost)
                    else:
                        dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j0][k - 1] + new_cost)
 
    # Result
    ans = min(dp[m - 1][j][target] for j in range(1, n + 1))
    return -1 if ans == inf else ans

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, implementing the same DP logic with minor syntactic variations. The key is the 3D DP table and the careful consideration of the state transitions based on whether a house is already painted or not.