Paint House III
Problem
A street has m houses in a row, and every house must end up in one of n colors numbered 1..n. Some houses were painted last summer: houses[i] is that color, or 0 if house i still needs paint — and an already-painted house must not be repainted. Painting house i with color j costs cost[i][j].
A neighborhood is a maximal block of consecutive houses sharing one color (so [1,2,2,1] has 3 neighborhoods). Return the minimum total cost to paint all remaining houses so the street has exactly target neighborhoods, or −1 if that is impossible.
houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 39def min_cost(houses, cost, m, n, target):
INF = float("inf")
# dp[j][k]: cheapest with house i in color j+1 and k neighborhoods
dp = [[INF] * (target + 1) for _ in range(n)]
for j in range(n):
if houses[0] == 0:
dp[j][1] = cost[0][j]
elif houses[0] == j + 1:
dp[j][1] = 0
for i in range(1, m):
ndp = [[INF] * (target + 1) for _ in range(n)]
for j in range(n):
if houses[i] and houses[i] != j + 1:
continue
paint = 0 if houses[i] else cost[i][j]
for k in range(1, target + 1):
same = dp[j][k]
diff = min((dp[p][k - 1] for p in range(n) if p != j), default=INF)
best = min(same, diff)
if best < INF:
ndp[j][k] = best + paint
dp = ndp
ans = min(dp[j][target] for j in range(n))
return -1 if ans == INF else ansfunction minCost(houses, cost, m, n, target) {
const INF = Infinity;
// dp[j][k]: cheapest with house i in color j+1 and k neighborhoods
let dp = Array.from({ length: n }, () => new Array(target + 1).fill(INF));
for (let j = 0; j < n; j++) {
if (houses[0] === 0) dp[j][1] = cost[0][j];
else if (houses[0] === j + 1) dp[j][1] = 0;
}
for (let i = 1; i < m; i++) {
const ndp = Array.from({ length: n }, () => new Array(target + 1).fill(INF));
for (let j = 0; j < n; j++) {
if (houses[i] !== 0 && houses[i] !== j + 1) continue;
const paint = houses[i] ? 0 : cost[i][j];
for (let k = 1; k <= target; k++) {
let best = dp[j][k];
for (let p = 0; p < n; p++)
if (p !== j && dp[p][k - 1] < best) best = dp[p][k - 1];
if (best < INF) ndp[j][k] = best + paint;
}
}
dp = ndp;
}
let ans = INF;
for (let j = 0; j < n; j++) ans = Math.min(ans, dp[j][target]);
return ans === INF ? -1 : ans;
}int minCost(int[] houses, int[][] cost, int m, int n, int target) {
final int INF = Integer.MAX_VALUE / 2;
// dp[j][k]: cheapest with house i in color j+1 and k neighborhoods
int[][] dp = new int[n][target + 1];
for (int[] row : dp) Arrays.fill(row, INF);
for (int j = 0; j < n; j++) {
if (houses[0] == 0) dp[j][1] = cost[0][j];
else if (houses[0] == j + 1) dp[j][1] = 0;
}
for (int i = 1; i < m; i++) {
int[][] ndp = new int[n][target + 1];
for (int[] row : ndp) Arrays.fill(row, INF);
for (int j = 0; j < n; j++) {
if (houses[i] != 0 && houses[i] != j + 1) continue;
int paint = houses[i] != 0 ? 0 : cost[i][j];
for (int k = 1; k <= target; k++) {
int best = dp[j][k];
for (int p = 0; p < n; p++)
if (p != j) best = Math.min(best, dp[p][k - 1]);
if (best < INF) ndp[j][k] = best + paint;
}
}
dp = ndp;
}
int ans = INF;
for (int j = 0; j < n; j++) ans = Math.min(ans, dp[j][target]);
return ans == INF ? -1 : ans;
}int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
const int INF = 1e9;
// dp[j][k]: cheapest with house i in color j+1 and k neighborhoods
vector<vector<int>> dp(n, vector<int>(target + 1, INF));
for (int j = 0; j < n; j++) {
if (houses[0] == 0) dp[j][1] = cost[0][j];
else if (houses[0] == j + 1) dp[j][1] = 0;
}
for (int i = 1; i < m; i++) {
vector<vector<int>> ndp(n, vector<int>(target + 1, INF));
for (int j = 0; j < n; j++) {
if (houses[i] != 0 && houses[i] != j + 1) continue;
int paint = houses[i] ? 0 : cost[i][j];
for (int k = 1; k <= target; k++) {
int best = dp[j][k];
for (int p = 0; p < n; p++)
if (p != j) best = min(best, dp[p][k - 1]);
if (best < INF) ndp[j][k] = best + paint;
}
}
dp = ndp;
}
int ans = INF;
for (int j = 0; j < n; j++) ans = min(ans, dp[j][target]);
return ans == INF ? -1 : ans;
}Explanation
The state needs three coordinates, which is what makes this a 3D DP: dp[i][j][k] = the cheapest way to paint houses 0..i such that house i ends up in color j and the street so far contains exactly k neighborhoods. Tracking the last color is unavoidable, because whether the next house starts a new neighborhood depends only on whether its color matches house i's.
The transition considers the previous house's color p. If p == j the new house joins the current block and k is unchanged: dp[i-1][j][k]. If p != j a new block opens, so it must have come from k−1 blocks: min over p of dp[i-1][p][k-1]. We add house i's paint cost — cost[i][j] if it is unpainted, 0 if it is already that color, and the state is simply forbidden (left at ∞) when the house is pre-painted in a different color.
The base case is house 0: it always opens the first neighborhood, so dp[0][j][1] equals its paint cost for each allowed color and everything else is ∞. Since layer i only reads layer i−1, the code keeps just two 2D slices (dp and ndp) and rolls the house dimension, which is exactly what the visualization shows layer by layer.
On the default example (houses = [0,0,0,0,0], 2 colors, target = 3) the cheapest reachable state evolves as 1 → 2 → 3 → 4 → 9: house 1 switches color cheaply (dp[1][c2][2] = 2), house 2 keeps color 2, house 3 switches back to color 1 reaching the third block, and house 4 keeps color 1 for 5, landing on dp[4][c1][3] = 9 with colors [1,2,2,1,1].
The answer is the cheapest cell of the last layer with k = target; if every such cell is still ∞, no assignment yields exactly target blocks and we return −1. Each of the m·n·target states scans n previous colors, giving O(m·n²·target) time, while the rolling layers keep memory at O(n·target).