There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color, and you need to cost the least. Return the minimum cost.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.
Input:[[14,2,11],[11,14,5],[14,3,10]]Output: 10Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost:2+5+3=10.
publicclassSolution {
// Color indicesprivatestaticfinalint RED = 0;
privatestaticfinalint BLUE = 1;
privatestaticfinalint GREEN = 2;
publicintminCost(int[][] costs) {
if (costs ==null|| costs.length== 0) {
return 0;
}
// Call the recursive function for each color starting on the first houseint costRed = paintHouse(0, RED, costs);
int costBlue = paintHouse(0, BLUE, costs);
int costGreen = paintHouse(0, GREEN, costs);
// Find the minimum of the three starting colorsreturn Math.min(costRed, Math.min(costBlue, costGreen));
}
privateintpaintHouse(int houseIndex, int color, int[][] costs) {
// Base case: If there are no more houses left to paintif (houseIndex == costs.length) {
return 0;
}
// Total cost of painting the current house with 'color'int totalCost = costs[houseIndex][color];
// Calculate the cost of painting the next house, ensuring we do not paint// the same color as the current house.if (color == RED) {
totalCost += Math.min(
paintHouse(houseIndex + 1, BLUE, costs),
paintHouse(houseIndex + 1, GREEN, costs));
} elseif (color == BLUE) {
totalCost += Math.min(
paintHouse(houseIndex + 1, RED, costs),
paintHouse(houseIndex + 1, GREEN, costs));
} else { // color == GREEN totalCost += Math.min(
paintHouse(houseIndex + 1, RED, costs),
paintHouse(houseIndex + 1, BLUE, costs));
}
return totalCost;
}
}
⏰ Time complexity: O(2^n). We know that for house 0, we have 3 choices of color. After that house [1..n] have 2 choices of color. So time complexity is O(2^n).
Let us observe the recursion tree for the first test case of sample test 2.
The root nodes are the possible colors for the first house, Cost(0, R), Cost(0, B), and Cost(0, G).
The next level nodes represent the costs of the second house given the color of the first house. For example, if the first house is painted red (Cost(0, R)), the second house can be painted either blue or green (Cost(1, B) or Cost(1, G)).
The tree continues in this manner, and each possible color decision for the current house leads to two more recursive calls for the next house, with the color options that don’t match the color selected for the current house.
The overlapping subproblems become evident when you notice that for calculating Cost(1, B), you need Cost(2, R) and Cost(2, G), and for Cost(1, G), you also need Cost(2, R) and Cost(2, G). Thus, subproblems like Cost(2, R) and Cost(2, G) are computed multiple times.
To avoid this redundancy, a typical DP solution would store the results of Cost(2, R) and Cost(2, G) after the first computation and then reuse these stored results, which is known as memoization. This technique significantly reduces the amount of computation needed to solve the problem, transforming it from exponential to linear time complexity.
classSolution {
privatestaticfinalint RED = 0;
privatestaticfinalint BLUE = 1;
privatestaticfinalint GREEN = 2;
private Integer[][] memo; // The memoization tablepublicintminCost(int[][] costs) {
if (costs ==null|| costs.length== 0) {
return 0;
}
int n = costs.length;
memo =new Integer[n][3]; // Initialize the memo table// Start the recursion from the first house and try each colorint costRed = paintHouse(0, RED, costs);
int costBlue = paintHouse(0, BLUE, costs);
int costGreen = paintHouse(0, GREEN, costs);
// Return the minimum cost among three starting colorsreturn Math.min(Math.min(costRed, costBlue), costGreen);
}
privateintpaintHouse(int houseIndex, int color, int[][] costs) {
if (houseIndex == costs.length) {
return 0; // Reached the end of houses }
// Check if the result is already computed and stored in memo tableif (memo[houseIndex][color]!=null) {
return memo[houseIndex][color];
}
int totalCost = costs[houseIndex][color]; // Current painting cost// Recursive calls for next house and different colors, excluding the current colorint nextCost = Integer.MAX_VALUE;
for (int nextColor = 0; nextColor < 3; nextColor++) {
if (nextColor != color) {
nextCost = Math.min(nextCost, paintHouse(houseIndex + 1, nextColor, costs));
}
}
// Add current cost to next cost and store result in memo table totalCost += nextCost;
memo[houseIndex][color]= totalCost;
return memo[houseIndex][color];
}
}
Let dp[i][j] be our dynamic programming matrix of N * 3 dimensions to store the minimum cost to paint first ‘i’ houses such that the i-th house is painted with j-th colour.
The dp array is used to store the minimum cost to paint up to the i-th house, ending with each of the three colors.
We start by initializing the dp array with the costs of painting the first house with each of the three available colors.
The algorithm then iteratively computes the minimum cost of painting each house in sequence, updating the dp table with the minimum cost that accounts for the constraint of not painting the same color as the previous house.
Finally, the lowest cost of painting the last house (with any color) will be the solution to the problem—that is, the total minimum cost to paint all houses while satisfying the no-color-repeat constraint.
publicclassHousePainting {
publicintminCost(int[][] costs) {
if (costs ==null|| costs.length== 0) {
return 0;
}
int n = costs.length;
int[][] dp =newint[n][3];
// Initialize the first row of DP table with the costs of the first house for each colorfor (int color = 0; color < 3; color++) {
dp[0][color]= costs[0][color];
}
for (int i = 1; i < n; i++) {
dp[i][0]= costs[i][0]+ Math.min(dp[i - 1][1], dp[i - 1][2]); // If we paint current house Red dp[i][1]= costs[i][1]+ Math.min(dp[i - 1][0], dp[i - 1][2]); // If we paint current house Blue dp[i][2]= costs[i][2]+ Math.min(dp[i - 1][0], dp[i - 1][1]); // If we paint current house Green }
return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
}
}