Paint House III: Neighborhood-Constrained DP

There are m houses in a row. Each house can be painted one of n colors, but some houses are already painted and cannot be changed. Consecutive houses with the same color form a "neighborhood." Your job is to paint the remaining houses so there are exactly target neighborhoods, and the total painting cost is minimized. If it is impossible, return -1.

This is 1473. Paint House III, and it is one of the best problems for learning multi-dimensional DP. The state space has three dimensions (house, color, neighborhood count), which sounds intimidating, but once you understand the transition logic, the solution is a clean triple loop.

Consider this example: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3. All houses are unpainted (0 means unpainted). The optimal painting is [1,1,2,2,1] with colors mapped to neighborhoods {1,1}, {2,2}, {1}, giving exactly 3 neighborhoods at a total cost of 9. The output is 9.

Why this problem matters

Paint House III teaches you how to handle a DP problem where the number of dimensions is larger than the usual one or two. Most DP problems you encounter early on are 1D (like House Robber) or 2D (like Edit Distance). Here, the DP state has three axes: which house you are considering, what color it gets, and how many neighborhoods have been formed so far. Learning to identify and structure a 3D DP state is a skill that transfers directly to other multi-dimensional problems.

The neighborhood counting constraint is also worth studying on its own. It is a "partition counting" constraint: you need to split the row of houses into exactly target contiguous groups. This type of constraint appears in problems about partitioning arrays, scheduling tasks into groups, and allocating resources into buckets.

The key insight

The number of neighborhoods formed so far depends entirely on whether consecutive houses share the same color. When you paint house i color j, the neighborhood count either stays the same (if house i-1 is also color j) or increases by one (if house i-1 is a different color). That means the transition from house i-1 to house i naturally updates the neighborhood count, and you can track it as part of the DP state without any extra bookkeeping.

This gives you the recurrence:

• If house i and house i-1 have the same color j: dp[i][j][k] = dp[i-1][j][k] + cost[i][j]
• If house i has color j and house i-1 has a different color p: dp[i][j][k] = dp[i-1][p][k-1] + cost[i][j]

You take the minimum over all valid predecessors.

The solution

def minCost(houses, cost, m, n, target):
    INF = float('inf')
    dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m)]

    for j in range(1, n + 1):
        if houses[0] != 0 and houses[0] != j:
            continue
        c = 0 if houses[0] != 0 else cost[0][j - 1]
        dp[0][j][1] = c

    for i in range(1, m):
        for j in range(1, n + 1):
            if houses[i] != 0 and houses[i] != j:
                continue
            c = 0 if houses[i] != 0 else cost[i][j - 1]
            for k in range(1, target + 1):
                same = dp[i - 1][j][k]
                diff = INF
                for p in range(1, n + 1):
                    if p != j:
                        diff = min(diff, dp[i - 1][p][k - 1])
                dp[i][j][k] = min(dp[i][j][k], min(same, diff) + c)

    ans = INF
    for j in range(1, n + 1):
        ans = min(ans, dp[m - 1][j][target])
    return ans if ans < INF else -1

The code initializes the first house, then iterates through the remaining houses. For each house-color-neighborhood triple, it checks two cases: the previous house had the same color (neighborhood count unchanged) or a different color (neighborhood count was one less). Pre-painted houses are handled by skipping any color that does not match the fixed color, and their painting cost is 0.

Visual walkthrough

The DP builds up row by row. At each house, you consider every possible color and every possible neighborhood count. The transition checks whether the new color matches the previous house's color (same neighborhood, count unchanged) or differs (new neighborhood, count incremented). Pre-painted houses restrict which colors are valid, reducing the work at those positions.

Complexity analysis

The 3D DP visits each (house, color, neighborhoods) state once. For each state, it checks up to n previous colors to find the best different-color predecessor. That inner loop over previous colors gives the n^2 factor. With m up to 100, n up to 20, and target up to 100, the total work is at most 100 * 400 * 100 = 4,000,000 operations, which runs comfortably within time limits.

The space can be reduced from O(m * n * target) to O(n * target) by keeping only two layers of the DP table (current house and previous house), since each house only depends on the previous one.

The building blocks

1. Multi-dimensional DP state

dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m)]

The core challenge is recognizing that the state needs three dimensions. The house index alone is not enough because the minimum cost depends on what color the house gets and how many neighborhoods have formed. Adding color and neighborhood count to the state captures all the information needed for the transition. This "add dimensions until the state is complete" pattern is the same one behind problems like Cherry Pickup II, where you track two positions simultaneously.

2. Same-vs-different color transition

same = dp[i - 1][j][k]
diff = INF
for p in range(1, n + 1):
    if p != j:
        diff = min(diff, dp[i - 1][p][k - 1])

The neighborhood count update is baked into the transition. When the previous house has the same color, k stays the same. When it has a different color, the current state uses k - 1 from the predecessor. This conditional counting pattern appears whenever you need to track contiguous groups, runs of identical elements, or segment boundaries in a sequence.

3. Handling pre-painted constraints

if houses[i] != 0 and houses[i] != j:
    continue
c = 0 if houses[i] != 0 else cost[i][j - 1]

Pre-painted houses add a constraint layer on top of the DP. If a house is already painted, you skip every color except its fixed one and set the painting cost to zero. This "fixed vs free" pattern appears in any DP problem where some decisions are locked in advance, such as placing queens on a partially filled board or filling in a Sudoku grid.

Edge cases

• All houses pre-painted. No choices to make. Just count the neighborhoods and check if the count equals target. If yes, cost is 0. If no, return -1.
• Target equals m. Every house must be a different color from its neighbor. If n is 1 and m > 1, this is impossible (return -1). Otherwise, greedily pick the cheapest non-matching color at each step.
• Target equals 1. All houses must be the same color. If some houses are pre-painted with different colors, return -1. Otherwise, pick the single color that minimizes total cost across all free houses.
• Single house. The answer is 0 if it is already painted (and target is 1), or the minimum cost[0][j] across all colors (and target is 1). If target is not 1, return -1.
• Impossible configurations. When target > m, you can never have more neighborhoods than houses, so return -1 immediately.

From understanding to recall

You have just walked through a 3D DP solution with same-vs-different color transitions and pre-painting constraints. The logic makes sense right now, but reproducing it under interview pressure is a different challenge. You need to remember the three-dimensional state, the two-case transition, the base case initialization for the first house, and the final scan across colors at the last house.

Spaced repetition closes the gap between understanding and recall. You revisit this problem at increasing intervals, writing the DP table setup and transition from scratch each time. After a few reps, the "house, color, neighborhoods" state template and the "same color keeps k, different color increments k" transition become automatic. You see a partition-counting constraint and your hands reach for the right DP structure without hesitation.

The multi-dimensional DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• House Robber - The simplest DP with a decision at each step, and a great warm-up before tackling multi-dimensional variants
• Coin Change - Classic 1D DP with an optimization objective, showing the same "try all options, take the best" structure
• Minimum Falling Path Sum - Grid DP with a choice of three directions, bridging the gap between 1D and multi-dimensional DP