256. Paint House

/**

 * 256. Paint House

 * There is a row of n houses, where each house can be painted one of 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 the 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.

*/

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/dynamic/PaintHouse.java

Leetcode has a very elegant description for this problem’s solution. Please have a look here: https://leetcode.com/problems/paint-house/solution/

I had coded a recursive solution to the problem as well as one using dynamic programming. You can see the recursive solution at github above. Here I will describe the solution as based on dynamic programming.

The dynamic programming approach here is extremely elegant. It essentially indicates that you start from the end and walk back to the first row while tracking the minimum possible cost so far.

The algorithm is as below:

1. First realize that the cost – color1 choice = cost color 1 of house 1 + min (color choice of house 2 colors 2 & 3), cost – color2, choice = cost color 2 of house 1 + min (color choice of house 2 colors 1 & 3), cost – color3 choice = cost color 3 of house 1 + min (color choice of house 2 colors 1 & 2). Min cost is min (color 1, color 2, color 3) above.
2. Iterate from last house to first
   1. At each iteration calculate min cost for each of the color choices, copy this cost into an array that can be used in the next iteration
   1. On next iteration leverage the previous cost (calculated in a) to calculate each of the costs of various colors
3. At the end minimum cost is minimum aggregated cost for any of the color choices

Here is the code:

public int minCostDP(int[][] costs) {
    if (costs.length == 0) return 0;
    int[] workRow = new int[numColors]; //an array for some background work
    int[] prevRow = new int[numColors]; //an array that tracks min costs so far per the color choices
    int currentRow = costs.length - 1;
    //copy the last costs to prev array and thereafter start from second last row
    System.arraycopy(costs[currentRow], 0, prevRow, 0, costs[currentRow].length);
    while (currentRow > 0) {
        currentRow--;
        //for each color calculate the min cost thus far
        workRow[0] = costs[currentRow][0] + Math.min(prevRow[1], prevRow[2]);
        workRow[1] = costs[currentRow][1] + Math.min(prevRow[0], prevRow[2]);
        workRow[2] = costs[currentRow][2] + Math.min(prevRow[0], prevRow[1]);
        //copy working array to previous array
        System.arraycopy(workRow, 0, prevRow, 0, workRow.length);
    }
    //the total cost so far per color choice is available in the prevRow
    //pick the min cost in the array
    return Math.min(Math.min(prevRow[0], prevRow[1]), prevRow[2]);
}