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.
1import java.util.Arrays;
2
3
This Java solution uses recursion with memoization to explore possible house coloring choices that achieve the target neighborhood count with minimum cost. The results of subproblems are stored in a memoization table to efficiently compute the overall result.