House Painting Problem

Problem Statement:  

The people of RGB Street have decided to paint each of their houses red,  green, or blue. They've also decided that no two neighboring houses will be  painted the same color. The neighbors of house i are houses i-1 and i+1. The  first and last houses are not neighbors.

  

You will be given a String[] houses, where the ith element corresponds to house i. Each element of houses will be formatted as "R G B" (quotes for clarity only), where R, G and B are the costs of painting the corresponding house red, green, and blue, respectively. Return the minimal total cost required to perform the work.

Definition:  

Constraints - houses will contain between 1 and 20 elements, inclusive. - Each element of houses will be in the format "R G B" (quotes for clarity only), where R, G and B are integers with no leading zeroes. - In each element of houses, the values R, G and B will be between 1 and 1000, inclusive.

  

Examples 0) {"1 100 100", "100 1 100", "100 100 1"} Returns: 3 "RGB" is the best choice, and the total cost of the work is equal to 3. 

  

  1) {"1 100 100", "100 100 100", "1 100 100"} Returns: 102 The minimum possible cost is 102, and there are two solutions that result in that cost: "RGR" and "RBR". 

  

  2) {"26 40 83", "49 60 57", "13 89 99"} Returns: 96 

  

  3) {"30 19 5", "64 77 64", "15 19 97", "4 71 57", "90 86 84", "93 32 91"} Returns: 208 

  

  4){"71 39 44", "32 83 55", "51 37 63", "89 29 100", "83 58 11", "65 13 15",  "47 25 29", "60 66 19"} Returns: 253

Solution: 

DP: we can paint the ith house with blue, red or green. so we have the following equations: 

cost[i,r] = min(cost[i-1,b], cost[i-1,g] ) + cost of painting i with r. 

cost[i,g] = min(cost[i-1,b], cost[i-1,r] ) + cost of painting i with g. 

cost[i,b] = min(cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.

  

Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);

int calcHouseColoringCost(int[][] M) {

int totalCost = 0;

int r = M.length + 1;

int c = M[0].length;

int[][] C = new int[r][c];

for (int i = 0; i < c; i++) {

C[0][i] = 0;

}

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

C[i][0] = Math.min(C[i - 1][1], C[i - 1][2]) + M[i - 1][0];

C[i][1] = Math.min(C[i - 1][2], C[i - 1][0]) + M[i - 1][1];

C[i][2] = Math.min(C[i - 1][0], C[i - 1][1]) + M[i - 1][2];

}

totalCost = Math.min(Math.min(C[r - 1][0], C[r - 1][1]), C[r - 1][2]);

return totalCost;

}