256 Paint House

There are a row ofnhouses, 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 anx3cost 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.

Note:
All costs are positive integers.

Example:

Input:
 [[17,2,17],[16,16,5],[14,3,19]]

Output:
 10

Explanation: 
Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.

class Solution {
    public int minCost(int[][] costs) {
        int n = costs.length;
        /**
            cost for n 
                cost for n - 1 houses + cost for house n
                  n - 1 .     n
                  blue .    green / red
                  green .   blue / red

                F[N][0] -> The cost of paint all n houses and paint the last house in red 
                F[N][0] = Math.min(F[N - 1][1] + costs[N - 1][0] , F[N-1][2] + cost[N-1][0])
        **/
        int[][] houses = new int[n + 1][3];
        houses[0][0] = houses[0][1] = houses[0][2] = 0;
        for (int i = 1; i <= n; i++) {
            //the color for house i is j
            for (int j = 0; j < 3; j++) {
                houses[i][j] = Integer.MAX_VALUE;
                //the color for house i - 1 is k
                for (int k = 0; k < 3; k++) {
                    if (j != k) {
                        houses[i][j] = Math.min(houses[i][j], houses[i-1][k] + costs[i-1][j]);
                    }
                }
            }
        }
        return Math.min(houses[n][0], Math.min(houses[n][1], houses[n][2]));
    }
}