Paint House III - Video Solutions

Problem Overview: You are given m houses and n colors. Some houses are already painted while others must be painted with a cost matrix. The goal is to minimize total painting cost while forming exactly target neighborhoods, where a neighborhood is a contiguous group of houses with the same color.

Approach 1: Memoization with DFS (Top‑Down DP) (Time: O(m * n^2 * target), Space: O(m * n * target))

This approach models the problem as a recursive decision process. At each house index you decide which color to paint. The state is defined by (index, prevColor, neighborhoods). If the current color differs from the previous one, the neighborhood count increases. Use DFS to explore painting choices and store results in a memo table so repeated states are computed once. When a house is already painted, the recursion simply continues with that color. This approach is easier to reason about because it mirrors the decision tree directly while memoization ensures the complexity stays manageable.

Approach 2: Dynamic Programming with 3D Array (Bottom‑Up) (Time: O(m * n^2 * target), Space: O(m * n * target))

The bottom‑up DP builds solutions iteratively. Define dp[i][c][k] as the minimum cost to paint houses up to index i, where house i has color c and exactly k neighborhoods have been formed. For each house, iterate through all possible colors and transition from every previous color. If the color changes, increment the neighborhood count; otherwise keep it the same. When a house is already painted, only that color is considered. The final answer is the minimum cost among dp[m-1][color][target]. This approach is deterministic and avoids recursion overhead, making it common in competitive programming solutions involving dynamic programming and multidimensional state transitions.

Both solutions rely heavily on tracking state transitions across houses, colors, and neighborhood counts. The cost matrix and house constraints are stored in simple arrays, while the optimization logic is handled through DP states built on top of arrays and cached subproblems.

Recommended for interviews: The bottom‑up 3D DP solution is typically what interviewers expect for this problem. It clearly shows how you design a DP state and manage transitions across multiple constraints. The memoized DFS version is still valuable during interviews because it demonstrates how you convert an exponential search into polynomial time using caching.