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.
1def minCost(houses, cost, m, n, target):
2 dp = [[[float('inf')] * (n + 1) for _ in range(target + 1)] for _ in range(m + 1)]
3 dp[0][0][0] = 0
4
5 for i in range(1, m + 1):
6 color = houses[i - 1]
7 for j in range(1, target + 1):
8 for k in range(1, n + 1):
9 if color != 0 and color != k:
10 continue
11
12 curr_cost = 0 if color != 0 else cost[i - 1][k - 1]
13
14 for p in range(1, n + 1):
15 if k == p:
16 dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][p] + curr_cost)
17 else:
18 dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][p] + curr_cost)
19
20 result = min(dp[m][target])
21 return -1 if result == float('inf') else resultThis Python function calculates the minimum cost to paint houses while forming the target number of neighborhoods. The solution involves iterating through each house and possible neighborhood configurations, adjusting costs based on whether a house is pre-painted or not.
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.