Sponsored
Sponsored
In this approach, we use a 3-dimensional dynamic programming table where dp[i][j][k] represents the minimum cost to paint up to the i-th house with j neighborhoods using color k on the i-th house. The goal is to fill this table and find the minimum value for the last house and target neighborhoods.
Time Complexity: O(m * target * n^2), as we iterate through every house, neighborhood, and color combination.
Space Complexity: O(m * target * n), for storing the dynamic programming table.
1function minCost(houses, cost, m, n, target) {
2 const dp = Array(m + 1).fill(null).map(() => Array(target + 1).fill(null).map(() => Array(n + 1).fill(Infinity)));
3 dp[0][0][0] = 0;
4
5 for (let i = 1; i <= m; i++) {
6 const color = houses[i - 1];
7 for (let j = 1; j <= target; j++) {
8 for (let k = 1; k <= n; k++) {
9 if (color !== 0 && color !== k) continue;
10
11 const currCost = color !== 0 ? 0 : cost[i - 1][k - 1];
12
13 for (let p = 1; p <= n; p++) {
14 if (k === p) {
15 dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][p] + currCost);
16 } else {
17 dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][p] + currCost);
18 }
19 }
20 }
21 }
22 }
23
24 const result = Math.min(...dp[m][target]);
25 return result === Infinity ? -1 : result;
26}This JavaScript solution uses a 3D dynamic programming array to calculate the minimal cost of painting all the houses to achieve exactly the target number of neighborhoods. It accounts for pre-painted houses by skipping coloring costs where applicable.
This approach applies memoization with a depth-first search (DFS) method to explore potential painting configurations. We recursively search for the minimum cost pathway to achieve the target neighborhood using memoized results to reduce redundant calculations.
Time Complexity: O(m * target * n), since each subproblem is solved independently.
Space Complexity: O(m * target * n), for the memoization table to store intermediate results.
1#include <vector>
2#include <algorithm>
3#include <memory.h>
4using namespace std;
5
class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
int memo[101][101][21];
memset(memo, -1, sizeof(memo));
int ans = dfs(memo, houses, cost, 0, m, n, target, 0);
return ans == 1e9 ? -1 : ans;
}
int dfs(int memo[101][101][21], vector<int>& houses, vector<vector<int>>& cost, int i, int m, int n, int target, int lastColor) {
if (target < 0) return 1e9;
if (i == m) return target == 0 ? 0 : 1e9;
if (memo[i][target][lastColor] != -1) return memo[i][target][lastColor];
if (houses[i] != 0) {
return memo[i][target][lastColor] = dfs(memo, houses, cost, i + 1, m, n, target - (houses[i] != lastColor), houses[i]);
}
int minCost = 1e9;
for (int color = 1; color <= n; color++) {
minCost = min(minCost, cost[i][color - 1] +
dfs(memo, houses, cost, i + 1, m, n, target - (color != lastColor), color));
}
return memo[i][target][lastColor] = minCost;
}
};This C++ implementation employs memoization and recursive exploration (DFS) to find the minimal cost to paint all houses while achieving exactly the target number of neighborhoods. Pre-colored houses are used to reduce unnecessary calculations.