LeetCode 1473: Paint House III
Problem Description
Explanation
To solve this problem, we can use dynamic programming with three states: house index, number of neighborhoods formed so far, and the last color used. We can iterate through each house, each neighborhood count, and each color to find the minimum cost. We also need to handle cases where the current house is already painted.
- Time Complexity: O(m * n * target * n) where m is the number of houses, n is the number of colors, and target is the given number of neighborhoods.
- Space Complexity: O(m * target * n) for the DP array.
Solutions
class Solution {
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int[][][] dp = new int[m + 1][target + 1][n + 1];
int INF = 1000000000;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= target; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = INF;
}
}
}
dp[0][0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int t = 1; t <= target; t++) {
int color = houses[i - 1];
for (int j = 1; j <= n; j++) {
if (color != 0 && color != j) {
continue;
}
int costCurrColor = (color == 0) ? cost[i - 1][j - 1] : 0;
for (int p = 1; p <= n; p++) {
if (j == p) {
dp[i][t][j] = Math.min(dp[i][t][j], dp[i - 1][t][p] + costCurrColor);
} else if (t > 1) {
dp[i][t][j] = Math.min(dp[i][t][j], dp[i - 1][t - 1][p] + costCurrColor);
}
}
}
}
}
int minCost = INF;
for (int j = 1; j <= n; j++) {
minCost = Math.min(minCost, dp[m][target][j]);
}
return (minCost == INF) ? -1 : minCost;
}
}Loading editor...