Last Updated: 11 Apr, 2021
Paint House II
Hard
Asked in companies
Ninja has started a painting business recently. He got a contract to paint ‘N’ houses in a city. Ninja has ‘K’ colors to choose from. But the client has a condition that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an N x K cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on.
Your task is to help Ninja to find the minimum cost required to paint houses according to this condition.
For Example :
Let say N = 2 and K = 3 and costs = [ [1,5,3] , [2,9,4] ]
In this case,
Ninja can paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5 .
Note :
Assume 0 based indexing
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains two integers ‘N’ and ‘K’ representing the number of houses and the number of colors available respectively.
The next ‘N’ line contains ‘K’ integers denoting the cost of painting i-th house with j-th color where 0 <= i < n & 0 <= j < k.
Output Format :
For each test case print the minimum cost of painting the houses.
Print the output of each test case in a separate line.
Note :
You do not need to print anything or take input. This already has been taken care of. Just implement the function.
Constraints :
1 <= T <= 5
1 <= n, k <= 10^4
1 <= costs[i][j] <= 10^3
Time limit: 1 sec
Approaches
For choosing a color for each house we have to keep two things in mind:
- Choosing the color having minimum cost.
- The chosen color is not chosen by the previous house.
We can solve this by a simple recursion in the following steps;
Algorithm
- Make a function int recursion( int lastColor, int currentHouse, int costs[][])
- The base case will be if the pointer to currentHouse == size of costs matrix then return 0.
- Initialize a variable ans equal to the maximum value of int.
- Iterate i from 0 to k.
- if(i != lastChosen colour)
- Then update ans recursively as ans = min (ans, costs[currentHouse][i]+ recursion( i, currentHouse+1, costs).
- Return ans.
We can solve this problem using a 2D dp array. For every house check cost of coloring it with k colors, then search the minimum cost (if not use certain color).
Algorithm
- First, handle the base case i.e. if costs == null or the number of houses is zero then return 0.
- Define dp[n][k], where dp[i][j] means for house i with color j the minimum cost.
- Initial value of dp arrays as dp[0][j] = costs[0][j].
- For others, dp[i][j] = max value of int.
- Iterate i from 1 to n.
- Iterate j from 0 to k.
- Iterate s from 0 to k.
- If s != j , i.e if jth color is not used for i-1th house then update dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + cost[i][j])
- Iterate s from 0 to k.
- Iterate j from 0 to k.
- Final state: Min(dp[n - 1][k]).
Algorithm
- If we choose the color[i][j], how could we reduce the comparision between (color[i-1][0] to color[i-1][k], except color[i-1][j])
- And we know there are actually extra comparisons since for each color, we have to find the smallest amongst other colors.
- Initialize two variables min_1 and min_2 , where min_1 = the lowest cost at the previous stage, min_2 = the 2nd lowest cost at the previous stage.
- We have the minimum costs for all colors at previous stage in color[i-1][k]
- Then, if we decide to paint house "i" with color "j", we can compute the minimum cost of other colors at "i-1" stage through following way.
- case 1: if "color[i-1][j] == min_1", it means the min_1 actually records the minimum value of color[i-1][j] (previous color is j), we have to use min_2;
- case 2: if "color[i-1][j] != min_1", it means min_1 is not the value of color[i-1][j] (previous color is not j), we can use the min_1's color.
- Note: if "pre_min_1 == pre_min_2", it means there are two minimum costs, anyway, no matter which color is pre_min_1, we can use pre_min_2
- Now if (dp[j] != pre_min_1 || pre_min_1 == pre_min_2) ,then update as dp[j] = pre_min_1 + costs[i][j].
- Else update as dp[j] = pre_min_2 + costs[i][j].
- The way to maintain "min_1" and "min_2"
- Iterate i from 0 to k
- If dp[i] <= min_1 , then min_2 = min_1 and min_1 = dp[i]
- Else if dp[i] < min_2 then min_2= dp[i].
- Finally return min_1.
Similar problems