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.
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.