There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.
A neighborhood is a maximal group of continuous houses that are painted with the same color.
houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].Given an array houses, an m x n matrix cost and an integer target where:
houses[i]: is the color of the house i, and 0 if the house is not painted yet.cost[i][j]: is the cost of paint the house i with the color j + 1.Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.
Example 1:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
Example 2:
Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}].
Cost of paint the first and last house (10 + 1) = 11.
Example 3:
Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.
Constraints:
m == houses.length == cost.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 104In 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.
This 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.
JavaScript
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.
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.
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.
C++
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D Array | Time Complexity: O(m * target * n^2), as we iterate through every house, neighborhood, and color combination. |
| Memoization with DFS | Time Complexity: O(m * target * n), since each subproblem is solved independently. |
House Robber III - Tree - Leetcode 337 • NeetCode • 46,887 views views
Watch 9 more video solutions →Practice Paint House III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor