Problem Explanation

We are given a task to paint a row of n houses. Each house can be painted with one of three colors (red, blue, or green) and the cost of painting each house with a given color varies. We need to paint all houses in such a way that no two adjacent houses share the same color.

The painting costs are represented by a 2D array where each sub-array contains three elements; the cost of painting a house with red, blue, or green respectively. For example, costs[2][1] would give us the cost of painting the 3rd house (since index starts at 0) with blue color.

Our task is to determine the minimum cost of painting all the houses with the given constraints.

For Example: If the Input is: [[17,2,17],[16,16,5],[14,3,19]] This means that the cost of painting 1st house with red color is 17, with blue is 2 and with green is 17. The cost of painting 2nd house with red is 16, with blue is 16 and with green is 5 and so on.

The output for the above input will be 10. This is because the optimal solution would be to paint the 1st house with blue (cost=2), the 2nd house with green (cost=5) and the 3rd house with blue (cost=3). Hence, the minimum cost is 2 + 5 + 3 = 10.

Approach

The solution of the problem can be obtained by using dynamic programming. We can use a bottom-up approach where we start tracking the minimum cost for painting each house starting from the first one. For each house, we calculate the price for painting it with each color, adding the cheaper cost to paint the neighbor houses into the current one's price.

Illustration

Using the input [[17,2,17],[16,16,5],[14,3,19]], this is how we can find the solution:

Starting at the second house, we find the minimum costs for painting it with each color:

• If we paint it red, we add the minimum cost between painting the previous house blue or green to the current cost. So, costs[1][0] += min(costs[0][1], costs[0][2]). That is 16 + min(2, 17) = 18.
• Similarly, for blue, we get costs[1][1] += min(costs[0][0], costs[0][2]). That is, 16 + min(17, 17) = 33.
• Finally, for green, we get costs[2][1] += min(costs[0][0], costs[0][1]). That is, 5 + min(17, 2) = 7.

By doing similar calculations for all the houses, we reach the last house. The minimum cost for painting all the houses will be the minimum value from the last row of the costs matrix. In our case, the minimum from [18, 33, 7] is 7, from [20, 18, 18] is 18 and from [21, 25, 25] is 21. Hence, the minimum cost will be 7.

Solution

Python

1
2python
3class Solution:
4    def minCost(self, costs: List[List[int]]) -> int:
5        if not costs:
6            return 0
7        for i in range(1, len(costs)):
8            # Calculate cost of painting the current house with each color
9            costs[i][0] += min(costs[i-1][1], costs[i-1][2])
10            costs[i][1] += min(costs[i-1][0], costs[i-1][2])
11            costs[i][2] += min(costs[i-1][0], costs[i-1][1])     
12        return min(costs[-1]) # Return the minimum cost from the last house

Java

1
2java
3class Solution {
4    public int minCost(int[][] costs) {
5        if(costs==null || costs.length==0)
6            return 0;
7
8        for(int i=1; i<costs.length; i++){
9            costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
10            costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
11            costs[i][2] += Math.min(costs[i-1][0],costs[i-1][1]);
12        }
13
14        return Math.min(Math.min(costs[costs.length-1][0], costs[costs.length-1][1]), costs[costs.length-1][2]);
15    }
16}

JavaScript

1
2javascript
3var minCost = function(costs) {
4    if(costs.length == 0)
5        return 0;
6    
7    for(let i=1 ; i<costs.length ; i++){
8        costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
9        costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
10        costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
11    }
12    
13    return Math.min(...costs[costs.length-1]);
14};

C++

1
2c++
3class Solution {
4public:
5    int minCost(vector<vector<int>>& costs) {
6        if(costs.empty())
7            return 0;
8        
9        for(int i=1; i<costs.size(); i++){
10            costs[i][0] += min(costs[i-1][1], costs[i-1][2]);
11            costs[i][1] += min(costs[i-1][0], costs[i-1][2]);
12            costs[i][2] += min(costs[i-1][0], costs[i-1][1]);
13        }
14
15        return *min_element(costs.back().begin(), costs.back().end());
16    }
17};

C#

1
2csharp
3public class Solution {
4    public int MinCost(int[][] costs) {
5        if (costs == null || costs.Length == 0)
6            return 0;
7            
8        for (int i = 1; i < costs.Length; i++){
9            costs[i][0] += Math.Min(costs[i-1][1], costs[i-1][2]);
10            costs[i][1] += Math.Min(costs[i-1][0], costs[i-1][2]);
11            costs[i][2] += Math.Min(costs[i-1][0], costs[i-1][1]);
12        }
13   
14        return Math.Min(Math.Min(costs[costs.Length - 1][0], costs[costs.Length - 1][1]), costs[costs.Length - 1][2]);
15    }
16}

This problem highlights a fundamental attribute of dynamic programming – overlapping sub-problems. We solve the problem for each house and use these solutions to solve the problem for the next houses. Here, the minimum cost for painting a house is dependent on the minimum cost for painting the previous houses. This "building-up" approach is a hallmark of dynamic programming.

It's worth noting that the solutions in Python, Java, JavaScript, C++, and C# are similar in logic and structure. They all follow a similar process:

1. Iterate over the houses starting from the second house to the last.
2. For each house, calculate the cost to paint it with each color, where the cost includes the cost of painting the house itself plus the minimum cost of painting the previous house with any of the other two colors.
3. Keep updating these costs in-place.
4. Finally, return the minimal cost among the three calculated for the last house.

However, there are subtle differences in syntax between different languages. These reflect the unique attributes of each language:

• Python and JavaScript manage to communicate the logic in the most concise way.
• Java and C# require a bit more code because of their nature of being statically-typed languages.
• C++ solution is very similar to that of Python, Java, and C# except we use min_element method to find the minimum cost from the last house.

Despite these differences, the strategy is the same, and with understanding, translation from one language to another is straightforward. Understanding these coding solutions will help prepare you for similar problems in the future. Remember, practice is the key to mastery.