- 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[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.

- Given an integer
**N**and a 2D array**cost[][3]**, where**cost[i][0]**,**cost[i][1]**, and**cost[i][2]**is the cost of painting**ith house**with colors**red**,**blue**, 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[][3] = {{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[][3] = {{1, 2, 3}, {1, 4, 6}}Output: 3

**Follow the steps below to solve the problem:**

- Create an auxiliary 2D dp[][3] array to store the minimum cost of previously colored houses.

- Initialize dp[0][0], dp[0][1], and dp[0][2] as the cost of cost[i][0], cost[i][1], and cost[i][2] respectively.

- Traverse the given array cost[][3] 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][0], dp[i][1], and dp[i][2] respectively.

- After completing the above steps, print the minimum of dp[N – 1][0], dp[N – 1][1], and dp[N – 1][2] 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.*; public class TechTwitter{ // 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][3]; // Base Case // Step 1 dp[0][0] = costs[0][0]; dp[0][1] = costs[0][1]; dp[0][2] = costs[0][2]; 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][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]; // If current house is colored // with blue the take min cost of // previous houses colored with // (red and green) dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]; // If current house is colored // with green the take min cost of // previous houses colored with // (red and blue) dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]; } System.out.println(Arrays.deepToString(dp)); // Print the min cost of the // last painted house System.out.println( Math.min(dp[N - 1][0], Math.min(dp[N - 1][1], dp[N - 1][2]))); } // 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