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[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 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[][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)

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS