Leetcode 1473. Paint House III

Problem Explanation:

In a small city, there's a straight row of ```

m```

houses which need to be painted from a selection of ```

n```

different colors. However, some houses have already been painted last summer, and can't be painted again this year. The goal is to paint all non-painted houses such that there are exactly ```

target```

"neighborhoods." A "neighborhood" constitutes an uninterrupted group of houses that have the same color. You're given an array ```

houses```

indicating the house colors (with 0 meaning no paint), a cost matrix ```

cost```

where ```

cost[i][j]```

reflects the cost to paint the i-th house with the (j+1)-th color, and a target number of neighborhoods. Your job is to determine the minimal cost required to complete this task, or return -1 if it's impossible.

This problem requires dynamic programming to solve efficiently in terms of time complexity.

Example:

Consider this example:

• 1

houses = [0,2,1,2,0]```

• 1

cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]```

• 1

m = 5, n = 2, target = 3```

• The output would be 11.
• Explanation:

Some houses are already painted, Paint the houses as [2,2,1,2,2]. This array contains target = 3 neighborhoods, [{2,2},{1},{2,2}]. Cost of painting the first and last house (10 + 1) = 11.

Approach:

This problem involves a dynamic programming approach where we create an array dp[][][] to store the minimum cost for painting the houses such that they form 'k' neighborhoods.

We check the following cases for every house:

• If a house was painted last year, we don't need to paint it again.

We check for other houses, and for every house, we have n choices. The goal is to choose a color that minimizes the total cost and forms exactly 'target' neighborhoods.

Another essential idea implemented in this solution is to keep checking the previous house color. If the current house's color is not the same as its previous house's color, we increment the neighborhood's count.

Now, let's write the solutions in Python, Java, JavaScript, C++, and C# language.

Python Solution:

1
2python
3class Solution:
4    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
5        @lru_cache(None)
6        def dp(i, target, color):
7            if target < 0 or i < 0:
8                return float('inf') if target else 0
9            
10            # If the house is pre-painted.
11            if houses[i]:
12                return dp(i-1, target-(color != houses[i]), houses[i])
13            
14            # If we need to paint the house.
15            return min(cost[i][c-1] + dp(i-1, target-(color != c), c) for c in range(1, n+1))
16        
17        answer = dp(m-1, target, 0)
18        return answer if answer < float('inf') else -1

Java Solution:

1
2java
3class Solution {
4    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
5        int[][][] dp = new int[m][n][target + 1];
6        int res = dfs(houses, cost, m, n, target, 0, 0, dp);
7        return (res == Integer.MAX_VALUE / 2) ? -1 : res;
8    }
9    private int dfs(int[] houses, int[][] cost, int m, int n, int target, int idx, int nei, int[][][] dp) {
10        if (idx == m || nei > target) {
11            return (nei == target) ? 0 : Integer.MAX_VALUE / 2;
12        }
13        if (houses[idx] != 0) {
14            int ch = houses[idx] - 1;
15            if (idx > 0 && houses[idx - 1] != ch + 1) nei++;
16            if (dp[idx][ch][nei] > 0) return dp[idx][ch][nei];
17            return dp[idx][ch][nei] = dfs(houses, cost, m, n, target, idx + 1, nei, dp);
18        }
19        if (dp[idx][n - 1][nei] > 0) return dp[idx][n - 1][nei];
20        int min = Integer.MAX_VALUE / 2;
21        for (int i = 0; i < n; i++) {
22            int temp = cost[idx][i] + dfs(houses, cost, m, n, target, idx + 1, (idx > 0 && houses[idx - 1] != i + 1) ? nei + 1 : nei, dp);
23            min = Math.min(min, temp);
24        }
25        return dp[idx][n - 1][nei] = min;
26    }
27}

JavaScript Solution:

1
2javascript
3var minCost = function(houses, costs, m, n, target) {
4    houses = houses.map(val => val - 1);
5    let dp = new Array(m)
6                .fill(0)
7                .map(() =>
8                    new Array(n)
9                    .fill(0)
10                    .map(() => new Array(target).fill(Number.MAX_SAFE_INTEGER))
11                );
12
13    if(houses[0] !== -1){
14        dp[0][houses[0]][0] = 0;
15    } else {
16        for(let j = 0; j < n; j++){
17            dp[0][j][0] = costs[0][j];
18        }
19    }
20
21    for(let i = 1; i < m; i++){
22        if(houses[i] !== -1){
23            for(let t = 0; t < target; t++){
24                for(let j = 0; j < n; j++){
25                    if(t >= j){
26                        dp[i][houses[i]][t] =
27                            Math.min(dp[i][houses[i]][t], dp[i-1][j][t] + (houses[i] !== j ? 1 : 0));
28                    }
29                }
30            }
31        } else {
32            for(let j = 0; j < n; j++){
33                for(let t = 0; t < target; t++){
34                    for(let k = 0; k < n; k++){
35                        if(t >= k){
36                            dp[i][j][t] =
37                                Math.min(dp[i][j][t], dp[i-1][k][t] + (j !== k ? 1 : 0) + costs[i][j]);
38                        }
39                    }
40                }
41            }
42        }
43    }
44
45    let res = Number.MAX_SAFE_INTEGER;
46
47    for(let j = 0; j < n; j++){
48        res = Math.min(res, dp[m-1][j][target-1]);
49    }
50
51    return res === Number.MAX_SAFE_INTEGER ? -1 : res;
52};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
6        vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(n+1, vector<int>(target+1, 1e6)));
7        
8        if(houses[0] != 0){
9            dp[0][houses[0]][1] = 0;
10        } else {
11            for(int i = 1;i<=n;++i){
12                dp[0][i][1] = cost[0][i-1];
13            }
14        }
15        
16        for(int i = 1;i<m;++i){
17            if(houses[i] != 0){
18                dp[i][houses[i]][1] = min(dp[i][houses[i]][1], dp[i-1][houses[i]][1]);
19                for(int j = 2;j<=target;++j){
20                    for(int k = 1;k<=n;++k){
21                        if(k != houses[i]){
22                            dp[i][houses[i]][j] = min(dp[i][houses[i]][j], dp[i-1][k][j-1]);
23                        }else{
24                            dp[i][houses[i]][j] = min(dp[i][houses[i]][j], dp[i-1][k][j]);
25                        }
26                    }
27                }
28            } else {
29                for(int j = 1;j<=n;++j){
30                    dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1] + cost[i][j-1]);
31                    for(int k = 2;k<=target;++k){
32                        for(int l = 1;l<=n;++l){
33                            if(l != j){
34                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][l][j-1] + cost[i][j-1]);
35                            }else{
36                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][l][j] + cost[i][j-1]);
37                            }
38                        }
39                    }
40                }
41            }
42        }
43        
44        int ans = 1e6;
45        for(int j = 1;j<=n;++j){
46            ans = min(ans, dp[m-1][j][target]);
47        }
48        return ans == 1e6 ? -1 : ans;
49    }
50};

C# Solution:

1
2csharp
3public class Solution {
4    int[,,,] dp;
5    int INF = (int)1e9;
6    public int MinCost(int[] houses, int[][] cost, int m, int n, int target) {
7        dp = new int[m+1,n+1,m+1,3];
8        for(int i=0; i<=m; i++)
9            for(int j=0; j<=n; j++)
10                for(int k=0; k<=m; k++)
11                     for(int l=0; l<3; l++)
12                        dp[i,j,k,l] = INF;
13        
14        if(houses[0] > 0)
15            dp[0,1,houses[0],1] = 0;
16        else
17            for(int i=1; i<=n; i++)
18                dp[0,1,i,1] = cost[0][i-1];
19        
20        for(int i=1; i<m; i++)
21        {
22            int h = houses[i];
23            if(h == 0){
24                for(int j=1; j<=i+1; j++)
25                    for(int k=0; k<=target; k++)
26                        for(int c=1; c<=n; c++)
27                        {
28                            int mint = Math.Min(dp[i-1,j,k,c], dp[i-1,j-1,k,c]);
29                            if(mint == INF) continue;
30                            for(int l=1; l<=n; l++){
31                                if(c==l) dp[i,j,c,2] = Math.Min(mint + cost[i][l-1],dp[i,j,c,2]);
32                                else
33                                    dp[i,j,c,1] = Math.Min(dp[i,j,c,1], mint+cost[i][l-1]);
34                            }
35                        }
36            }
37            else{
38                for(int j=1; j<=i+1; j++)
39                    for(int k=0; k<=target; k++)
40                        for(int c=1; c<=n; c++)
41                        {
42                            int mint = Math.Min(dp[i-1,j,k,c], dp[i-1,j-1,k,c]);
43                            if(mint == INF) continue;
44                            if(h==c) dp[i,j,c,2] = Math.Min(dp[i,j,c,2], mint);
45                            else
46                                    dp[i,j,h,1] = Math.Min(dp[i,j,h,1], mint);
47                        }
48            }
49        }
50
51        int minCost = INF;
52        for(int j=1; j<=target; j++)
53            for(int i=1; i<=n; i++)
54            minCost = Math.Min(minCost, dp[m-1,j,i,2]);
55        return minCost==INF?-1:minCost;
56    }
57}

These solutions use a 3D dynamic programming approach to solve the problem, where we take into consideration 3 factors - the index of the current house, the color painted on the current house, and the number of neighborhoods formed so far.

In all solutions, we start by defining a 3D table, dp[][][]. This works as a bottom-up approach in dynamic programming, where we start filling up the table from base cases and then proceed and fill up the entire table using previously computed sub-problems stored in the table itself.

Each language solution does this slightly differently due to the differences in their syntax and language features.

In the Python solution, we use a Python decorator called @lru_cache(None), which stores the results of expensive function calls and re-uses the results when the same inputs occur again, hence reducing the time complexity of the solution. The None argument specifies that there's no limit on the number of cached values.

Java Solution uses a recursive approach and dynamic programming to solve this problem. We initialized our 3D DP array with m houses, n colors, and target neighborhoods. We recursively calculate the minimum cost and store it in our dynamic programming array.

The JavaScript's solution uses a nested loop to iterate over all possible states our dynamic programming solution can have. The final solution is then retrieved from the last accessible state.

In C++, we start by initializing a 3D dynamic programming table with a size of (n + 1) * (m + 1) * (target + 1). This array is filled initially with a large number. Then we check the color of each house and update our dp array accordingly. In the end, we return the smallest value at the target's positions.

C# Solution firstly initializes a 4D DP array with m+1 houses, n+1 colors, m+1 neighborhoods, and the state of the house. The fourth dimension indicates whether a state is finished or not. If it's finished, it means there isn't any operation that can change its current value. Here, the cost of painting will be 0. For the other states, we have to add the cost of painting the houses.

The time complexity for all solutions can approximately be considered as O(mn^2target) and space complexity as O(mntarget).