Friend, we bring you yet another question "Paint House". This question is a famous problem of Leetcode. We are going to attempt it in this article.
Have you read the problem statement?
Let's discuss it.
Important Links : Problem Link, Solution Video
Prev Next
Paint House
Problem Discussion :
- You are given a number n, representing the number of houses.
- In the next n rows, you are given 3 space separated numbers representing the cost of painting nth house with red or blue or green color.
- You are required to calculate and print the minimum cost of painting all houses without painting any consecutive house with the same color.
This question uses the same trick as the previous question, "Maximum Sum Non-adjacent Elements". Refer to that question if you haven't already.
Let's understand this problem through the example given in the problem statement.
In figure 1,the x-axis denotes the number of houses and the y-axis denotes the colors they are to be painted with. These colors are red, blue and green.
For example, the first cell of the first row and column denotes that the cost of painting House no. '1' with red color is 1.
So, we are required to paint a house with a color such that no adjacent houses are painted with the same color.
Hence, just like in the question "Maximum Sum Non-Adjacent Elements", if a color is included in the previous house then it has to be excluded from the current house.
Let's discuss the solution part now.
Approach :
STORAGE & MEANING
We make an array for DP of the dimensions same as that of the input array i.e. 3*n.
The meaning assigned to a single cell in this grid is that "if we paint the house at hand with a color then what will be the minimum cost for it".
DIRECTION
We always try to solve the question for a simpler and smaller problem via which we move on to the bigger problem.
We want you to meditate on the fact that if we had started from the first column i.e. for the first house, then the minimum cost will be the same as that of the input cost.
This is possible because the painting of the first house is not dependent on the colors of any other house.
Figure 2 is the DP array (drawn in green to differentiate from the input array).
Now let's discuss the traversal for house 2.
We ask ourselves, if it's mandatory to paint the second house with red color, what will be the minimum cost such that no adjacent houses have the same color.
For that we paint house 2 with Red but make sure that house 1 is not painted with it. This means that now house 1 has to choose from paints blue and green. So, it will choose the paint which has the minimum cost. In this case, the cost of blue=5 and cost of green =7.Hence, blue is chosen.
According to our above discussion, the minimum cost to paint House 2 with red is the sum of the cost of red paint for house 2 and the minimum cost of the remaining 2 colors for house 1 i.e. 5+5=10.
Same method is used to find the minimum cost of the rest of the colors.
We want you to try filling this new DP array yourself and then check your answer with ours.
We want you to refer to "Paint House" Solution video for a better understanding of the traversal.
Eventually our final answer will be the minimum cost of all the paints for house 4. This is so because the painting of house 4 is dependent on the rest of the houses such that our conditions are satisfied.
Hence the minimum out of the cost of red, the cost of blue and the cost of green i.e. 8, 10 and 11 is 8.
So our answer to the problem is 8.
You must have got a little hang of dynamic programming questions by now , which is why we want you to first give writing the code a try yourself. Don't beat yourself up if you are not able to. DP problems can be a bit tricky.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
int[][]arr=new int[n][3];
for(int i=0;i< n;i++){
for(int j=0;j<3;j++){ //1
arr[i][j]=scn.nextInt();
}
}
int[][] dp=new int[n][3]; //2
dp[0][0]=arr[0][0];
dp[0][1]=arr[0][1]; //3
dp[0][2]=arr[0][2];
for(int i=1;i< n;i++){ //4
dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0];
dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+arr[i][1];
dp[i][2]=Math.min(dp[i-1][1],dp[i-1][0])+arr[i][2];
}
System.out.println(Math.min(dp[n-1][0],(Math.min(dp[n-1][1],dp[n-1][2]))));
//5
}
}
java;
true";
CODE DISCUSSION
- Array arr[n][3] is taken as the input array.
- We make a new array dp[n][3] with the same dimensions as arr where each cell stores the minimum cost if we paint the house with only one color such that no adjacent houses have the same color.
- As already discussed, the minimum cost of each cell for column of house 1 will be the same as that of the input cost.
- We traverse the loop for all houses from house 2. The minimum cost to paint a House with one color is to take the sum of input cost of that paint and the minimum cost of the remaining 2 colors for the previous house.
- Eventually our final answer will be the minimum out of the costs of all the paints for the last house. This is so because the painting of the last house is dependent on painting the rest of the houses such that our conditions are satisfied.
Analysis
Time Complexity :
O(n2)
This time complexity is quadratic because of the use of nested for loop.
SPACE COMPLEXITY :
O(n2)
As an extra space is required for a 2D dynamic programming array, therefore space complexity is quadratic.
We encourage you to watch the video "Paint Houses" for a clearer explanation of this problem.
With this we conclude our question "Paint Houses". We'll bring you many such interesting questions as we move further along the lecture. So keep with us on this path of Dynamic Programming!
