## Tuesday, May 17, 2022

### Easy_Question17 :Minimize cost of painting N houses such that adjacent houses have different colors

• 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.
• The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs is the cost of painting house 0 with color red; costs is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

• Given an integer N and a 2D array cost[], where cost[i]cost[i], and cost[i] is the cost of painting ith house with colors redblue, and green respectively, the task is to find the minimum cost to paint all the houses such that no two adjacent houses have the same color.
`Examples:Input: N = 3, cost[] = {{14, 2, 11}, {11, 14, 5}, {14, 3, 10}}Output: 10Explanation: Paint house 0 as blue. Cost = 2.Paint house 1 as green. Cost = 5. Paint house 2 as blue. Cost = 3.Therefore, the total cost = 2 + 5 + 3 = 10.Input: N = 2, cost[] = {{1, 2, 3}, {1, 4, 6}}Output: 3`

Follow the steps below to solve the problem:

• Create an auxiliary 2D dp[] array to store the minimum cost of previously colored houses.
• Initialize dp, dp, and dp as the cost of cost[i], cost[i], and cost[i] respectively.
• Traverse the given array cost[] over the range [1, N] and update the cost of painting the current house with colors red, blue, and green with the minimum of the cost other two colors in dp[i], dp[i], and dp[i] respectively.
• After completing the above steps, print the minimum of dp[N – 1], dp[N – 1], and dp[N – 1] as the minimum cost of painting all the houses with different adjacent colors.
Solution
```// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;

// Function to find the minimum cost of
// coloring the houses such that no two
// adjacent houses has the same color
static void minCost(int costs[][], int N)
{

// Corner Case
if (N == 0)
return;

// Auxiliary 2D dp array
int dp[][] = new int[N];

// Base Case // Step 1
dp = costs;
dp = costs;
dp = costs;

for (int i = 1; i < N; i++) {

// If current house is colored
// with red the take min cost of
// previous houses colored with
// (blue and green)
dp[i] = Math.min(dp[i - 1], dp[i - 1])
+ costs[i];

// If current house is colored
// with blue the take min cost of
// previous houses colored with
// (red and green)
dp[i] = Math.min(dp[i - 1], dp[i - 1])
+ costs[i];

// If current house is colored
// with green the take min cost of
// previous houses colored with
// (red and blue)
dp[i] = Math.min(dp[i - 1], dp[i - 1])
+ costs[i];
}

System.out.println(Arrays.deepToString(dp));

// Print the min cost of the
// last painted house
System.out.println(
Math.min(dp[N - 1],
Math.min(dp[N - 1], dp[N - 1])));
}

// Driver code
public static void main(String[] args)
{

int costs[][] = { { 14, 2, 11 },
{ 11, 14, 5 },
{ 14, 3, 10 } };

int N = costs.length;

// Function Call
minCost(costs, N);
}
}```

Visualizer after step 1 in the above code

## You may also like

a
Kubernetes AWS Java Coding Question
Microservices Core Java Python
Spring Framework AI/MLSpring Boot