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[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: 10

Explanation: 
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 

Visualizer after first Iteration of for loop in the above code 

Visualizer after the second  iteration of for loop in the above code 

Time Complexity: O(N)
Auxiliary Space: O(N)