Welcome to Subscribe On Youtube
1473. Paint House III
Description
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.
- For example:
houses = [1,2,2,3,3,2,1,1]contains5neighborhoods[{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 housei, and0if the house is not painted yet.cost[i][j]: is the cost of paint the houseiwith the colorj + 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] <= 104
Solutions
-
class Solution { public int minCost(int[] houses, int[][] cost, int m, int n, int target) { int[][][] f = new int[m][n + 1][target + 1]; final int inf = 1 << 30; for (int[][] g : f) { for (int[] e : g) { Arrays.fill(e, inf); } } if (houses[0] == 0) { for (int j = 1; j <= n; ++j) { f[0][j][1] = cost[0][j - 1]; } } else { f[0][houses[0]][1] = 0; } for (int i = 1; i < m; ++i) { if (houses[i] == 0) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= Math.min(target, i + 1); ++k) { for (int j0 = 1; j0 <= n; ++j0) { if (j == j0) { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]); } else { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]); } } } } } else { int j = houses[i]; for (int k = 1; k <= Math.min(target, i + 1); ++k) { for (int j0 = 1; j0 <= n; ++j0) { if (j == j0) { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]); } else { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]); } } } } } int ans = inf; for (int j = 1; j <= n; ++j) { ans = Math.min(ans, f[m - 1][j][target]); } return ans >= inf ? -1 : ans; } } -
class Solution { public: int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) { int f[m][n + 1][target + 1]; memset(f, 0x3f, sizeof(f)); if (houses[0] == 0) { for (int j = 1; j <= n; ++j) { f[0][j][1] = cost[0][j - 1]; } } else { f[0][houses[0]][1] = 0; } for (int i = 1; i < m; ++i) { if (houses[i] == 0) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= min(target, i + 1); ++k) { for (int j0 = 1; j0 <= n; ++j0) { if (j == j0) { f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]); } else { f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]); } } } } } else { int j = houses[i]; for (int k = 1; k <= min(target, i + 1); ++k) { for (int j0 = 1; j0 <= n; ++j0) { if (j == j0) { f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]); } else { f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]); } } } } } int ans = 0x3f3f3f3f; for (int j = 1; j <= n; ++j) { ans = min(ans, f[m - 1][j][target]); } return ans == 0x3f3f3f3f ? -1 : ans; } }; -
class Solution: def minCost( self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int ) -> int: f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)] if houses[0] == 0: for j, c in enumerate(cost[0], 1): f[0][j][1] = c else: f[0][houses[0]][1] = 0 for i in range(1, m): if houses[i] == 0: for j in range(1, n + 1): for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min( f[i][j][k], f[i - 1][j][k] + cost[i][j - 1] ) else: f[i][j][k] = min( f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1] ) else: j = houses[i] for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]) else: f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]) ans = min(f[-1][j][target] for j in range(1, n + 1)) return -1 if ans >= inf else ans -
func minCost(houses []int, cost [][]int, m int, n int, target int) int { f := make([][][]int, m) const inf = 1 << 30 for i := range f { f[i] = make([][]int, n+1) for j := range f[i] { f[i][j] = make([]int, target+1) for k := range f[i][j] { f[i][j][k] = inf } } } if houses[0] == 0 { for j := 1; j <= n; j++ { f[0][j][1] = cost[0][j-1] } } else { f[0][houses[0]][1] = 0 } for i := 1; i < m; i++ { if houses[i] == 0 { for j := 1; j <= n; j++ { for k := 1; k <= target && k <= i+1; k++ { for j0 := 1; j0 <= n; j0++ { if j == j0 { f[i][j][k] = min(f[i][j][k], f[i-1][j][k]+cost[i][j-1]) } else { f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1]+cost[i][j-1]) } } } } } else { j := houses[i] for k := 1; k <= target && k <= i+1; k++ { for j0 := 1; j0 <= n; j0++ { if j == j0 { f[i][j][k] = min(f[i][j][k], f[i-1][j][k]) } else { f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1]) } } } } } ans := inf for j := 1; j <= n; j++ { ans = min(ans, f[m-1][j][target]) } if ans == inf { return -1 } return ans } -
function minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number { const inf = 1 << 30; const f: number[][][] = new Array(m) .fill(0) .map(() => new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(inf))); if (houses[0] === 0) { for (let j = 1; j <= n; ++j) { f[0][j][1] = cost[0][j - 1]; } } else { f[0][houses[0]][1] = 0; } for (let i = 1; i < m; ++i) { if (houses[i] === 0) { for (let j = 1; j <= n; ++j) { for (let k = 1; k <= Math.min(target, i + 1); ++k) { for (let j0 = 1; j0 <= n; ++j0) { if (j0 === j) { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]); } else { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]); } } } } } else { const j = houses[i]; for (let k = 1; k <= Math.min(target, i + 1); ++k) { for (let j0 = 1; j0 <= n; ++j0) { if (j0 === j) { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]); } else { f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]); } } } } } let ans = inf; for (let j = 1; j <= n; ++j) { ans = Math.min(ans, f[m - 1][j][target]); } return ans >= inf ? -1 : ans; }