Redirecting to
NADOS


  Prev   Next

Paint House-Many Colors







If you can't explain it simply, you don't understand it well enough.
~ Albert Einstein

Paint House-Many Colors

Welcome Back Readers!

Our next problem is "Paint House-Many Colors" of "Dynamic Programming". It is a very interesting problem. This question is just an extension of the previous question that is Paint House. So that's why, it is advised that you follow the sequence of questions available on our website.

Important Links : Problem Link, Solution Video

If you have already solved that problem, then this one will be easy for you to understand as it will give you a broader perspective to visualize it and if you haven't solved it then Please solve that question first.

Let's move to the problem.

Problem Discussion :

In this problem you are given a number n and a number k in separate lines, representing the number of houses and number of colors.

In the next n rows, you are given k space separated numbers representing the cost of painting the house with one of the k colors.

You are required to calculate and print the minimum cost of painting all houses without painting any consecutive house with the same color.


For example:

Input: 4 6

1 5 7

5 8 4

3 2 9

1 2 4

Output: 8


How? Well we will see that soon.

You can also check part of the video on this problem to understand it in a better way.

Approach :

So taking an example, where n = 4 (number of houses) and k = 6 (color options: c1, c2, c3, c4, c5, c6). And corresponding cost of color of painting the House (h1, h2, h3 and h4) with colors (c1, c2, c3, c4 ,c5, c6) respectively is shown in figure. Our aim is to minimize the total cost of painting all 4 houses such that no 2 consecutive houses have the same color.

img
  • Now we will prepare a dp[][] matrix for storing the minimal total cost at each level while considering choosing each color without violating the condition.
  • But before moving further, make sure that you first fill, row of dp with corresponding value of cost of color to paint house 1 because the total minimal cost to paint house 1 when choosing one color option at a time will simply be the cost of painting house 1 with corresponding color.
  • That means if we are to paint house 2 with color 4 then we will look for minimal cost of painting house 1 except the cost of color 4 itself (so that the condition of 2 consecutive houses with the same color does get violated) and add cost of color 4 in painting house 2.
  • So the minimal cost of painting house 1 excluding the option for color 4 itself is 1 and adding the cost of painting house 2 with color 4 i.e. 3 we get 4, so we will store 4 in dp matrix at (h2, c2).
  • In a similar pattern we fill each and every index of dp[]. In the above diagram, we have filled the dp till house 3. Try to fill dp for house 4 (i.e. fourth row )

Let's try to code this.

First of all we take input for n (number of houses), k (number of colors) and in the next n rows, for k space separated numbers representing the cost of painting nth house with one of the k colors.

img

Then we define a n*k 2d array and fill its first row with cost of painting house 1 for different color.

img

Then we apply a nested for loop for traversing dp for filling it. Inside it we initially define it for maximum value. Then we find the minimum value of the previous row excluding the value of the corresponding color at which we are now in order to avoid 2 houses of similar color. After finding the minimum value, we add this to the current value of color j of house i and store it in corresponding dp.

img

After filling all the rows successfully using the above code, we need to find the minimum of the last row in order to have our final answer.

img
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 k = scn.nextInt(); int[][] arr = new int[n][k]; for (int i = 0; i < n; i++) { for(int j = 0; j < k; j++){ arr[i][j] = scn.nextInt(); } } int[][] dp = new int[arr.length][arr[0].length]; for(int j = 0; j < arr.length[0]; j++){ dp[0][j] = arr[0][j]; } for (int i = 0; i < dp.length; i++) { for(int j = 0; j < dp[0].length; j++){ int min = Integer.MAX_VALUE; for(int k = 0; k < dp[0].length; k++){ if(){ if(dp[i - 1] [k] < min){ min = dp[i - 1][k]; } } } dp[i][j] = arr[i][j] + min; } } int min = Integer.MAX_VALUE; for( int k = 0; k < dp[0].length; k++){ if(dp[n - 1][k]) < min){ min = dp[i - 1][k]; } } System.out.print(min); } }
java; true";

We use long because of the constraints given in the problem.

Analysis
Time Complexity :

O(n*k^2)

The outer loop is running dp.length times i.e n times. But the inner loops are running dp[0].length times i.e. k times. So the time complexity will be O(n*k2).

SPACE COMPLEXITY :

O(n*k)

Since we have used 2d array variables which take n*k space, it is O(n*k).

We hope that this article was helpful. You must check out our solution video for more clear understanding. We want you to dry run your code for different values of n and k.

Thought process of this question resembles a couple of previous problems which we have already discussed. Also if you remember about permutation and combination then understanding this kind of problem will be beneficial.

Forgive yourself and stay focused. Until then keep thinking and solving new problems on Dynamic Programming. All the best!

Happy Coding!

Arrays
Dynamic Programming
Author: Nikita Aggarwal
 
Run
Id Name