#1473

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Paint House III

Solve Paint House III using state transition dynamic programming to minimize painting costs while forming exact neighborhoods efficiently.

array dynamic programming

Problem Statement

You are given a row of m houses in a small city, each house can be painted with one of n colors. Some houses are already painted and must remain unchanged. Painting each unpainted house with a color incurs a specific cost provided in a matrix.

A neighborhood is defined as a maximal group of consecutive houses painted the same color. Given the houses array, the cost matrix, and a target number of neighborhoods, determine the minimum total cost to paint the houses to form exactly target neighborhoods. If it is impossible, return -1.

Examples

Example 1

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3

Output: 9

Paint houses of this way [1,2,2,1,1] This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}]. Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3

Output: 11

Some houses are already painted, Paint the houses of this way [2,2,1,2,2] This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. Cost of paint the first and last house (10 + 1) = 11.

Example 3

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3

Output: -1

Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Constraints

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 104

Solution Approach

Dynamic Programming State Definition

Define a DP state dp[i][k][c] representing the minimum cost to paint the first i houses forming k neighborhoods with the i-th house painted color c. This state captures the key pattern of tracking previous decisions to compute optimal costs while maintaining the exact neighborhood count.

State Transition

For each house, iterate over possible colors. If the color matches the previous house, the neighborhood count remains; otherwise, increment it. Update dp[i][k][c] with the minimum of existing value and previous state plus current paint cost. Already painted houses skip cost addition but enforce color constraints.

Result Extraction

After processing all houses, the minimum value among dp[m-1][target][*] gives the answer. If all states for target neighborhoods remain infinity, return -1. This approach prevents overcounting neighborhoods and ensures minimal total cost.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on m, n, and target. Standard DP leads to O(m * n * target * n) time and O(m * target * n) space, reflecting iteration over houses, colors, and neighborhood states.

What Interviewers Usually Probe

Consider edge cases where houses are already painted and may limit valid neighborhood formation.
Check for impossibility early if initial painted houses exceed target neighborhoods.
Optimize state transitions to avoid redundant recalculations for all color combinations.

Common Pitfalls or Variants

Common pitfalls

Ignoring already painted houses and adding paint costs incorrectly.
Incorrectly incrementing neighborhood count when consecutive houses have the same color.
Overlooking cases where forming exactly target neighborhoods is impossible, returning wrong cost.

Follow-up variants

Change the neighborhood definition to allow non-consecutive same-colored houses and track differently in DP.
Introduce additional constraints like limiting specific colors for certain houses.
Optimize for large n by pruning DP states using memoization of only feasible previous color transitions.

FAQ

What is the main dynamic programming pattern in Paint House III?

The problem uses state transition DP, where each state tracks the current house index, number of neighborhoods formed, and last painted color to determine minimal costs.

How do I handle houses that are already painted?

Skip cost addition for painted houses and enforce their color in the DP state transitions, ensuring neighborhoods are counted correctly.

What if it's impossible to form the exact target neighborhoods?

If no DP state reaches the target number of neighborhoods, return -1 as required by the problem statement.

Can the DP approach handle the maximum constraints efficiently?

Yes, by iterating over m, n, and target states with proper pruning and memoization, the solution remains feasible for m <= 100 and n <= 20.

Why is state transition DP necessary for Paint House III?

Because each house's paint choice affects neighborhood formation and total cost, DP efficiently tracks all feasible sequences to guarantee exact target neighborhoods.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j][k]$ to represent the minimum cost to paint houses from index $0$ to $i$, with the last house painted in color $j$, and exactly forming $k$ blocks. The answer is $f[m-1][j][\textit{target}]$, where $j$ ranges from $1$ to $n$. Initially, we check if the house at index $0$ is already painted. If it is not painted, then $f[0][j][1] = \textit{cost}[0][j - 1]$, where $j \in [1,..n]$. If it is already painted, then $f[0][\textit{houses}[0]][1] = 0$. All other values of $f[i][j][k]$ are initialized to $\infty$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class Solution:
    def minCost(
        self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
    ) -> int:
        f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
        if houses[0] == 0:
            for j, c in enumerate(cost[0], 1):
                f[0][j][1] = c
        else:
            f[0][houses[0]][1] = 0
        for i in range(1, m):
            if houses[i] == 0:
                for j in range(1, n + 1):
                    for k in range(1, min(target + 1, i + 2)):
                        for j0 in range(1, n + 1):
                            if j == j0:
                                f[i][j][k] = min(
                                    f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]
                                )
                            else:
                                f[i][j][k] = min(
                                    f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]
                                )
            else:
                j = houses[i]
                for k in range(1, min(target + 1, i + 2)):
                    for j0 in range(1, n + 1):
                        if j == j0:
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j][k])
                        else:
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1])

        ans = min(f[-1][j][target] for j in range(1, n + 1))
        return -1 if ans >= inf else ans

Continue Practicing

#1477 find two non overlapping sub arrays each with target sum #1478 allocate mailboxes #1467 probability of a two boxes having the same number of distinct balls