256. Paint-House

difficulty: Easy

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.

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.

Method One

class Solution {
    private int numberOfColors;
    public int minCost(int[][] costs) {
        if(costs.length < 1 ) {
            return 0;
        }
        this.numberOfColors = costs[0].length;
        int[] prevMinCostByColor = new int[ numberOfColors ];
        
        for(int i = 0; i < costs.length; i++ ) {
            
            int[] curMinCostByColor = new int[ numberOfColors ];
            
            for(int c1 = 0; c1 < numberOfColors; c1++ ) {
                int min = Integer.MAX_VALUE;
                for(int c2 = 0; c2 < numberOfColors; c2++ ) {
                    if( c1 == c2 ) {
                        continue;
                    }
                    min = Math.min(min, prevMinCostByColor[c2]);
                }
                curMinCostByColor[c1] = min + costs[i][c1];
            }
            prevMinCostByColor = curMinCostByColor;
        } 
        
        int minCost = Integer.MAX_VALUE; 
        for(int c = 0; c < numberOfColors; c++ ) {
            minCost = Math.min(minCost, prevMinCostByColor[c] );
        }
        return minCost;
    }
}
​
​
/**
对于 第 N 个房子的 第 c 个颜色来说。
它可以选择和上个房子不同的颜色。因此而 dp 的。
对于这个题只需要如下这么写就好了。
*/

class Solution {
public int minCost(int[][] costs) {
// dp[i][j] means current total lowest cost with painting house i with color j

        int[][] dp = new int[costs.length + 1][3];
        for(int i = 0; i < costs.length; i++) {
            dp[i + 1][0] = costs[i][0] + Math.min(dp[i][1], dp[i][2]);
            dp[i + 1][1] = costs[i][1] + Math.min(dp[i][0], dp[i][2]);
            dp[i + 1][2] = costs[i][2] + Math.min(dp[i][0], dp[i][1]);
        }
        return Math.min(Math.min(dp[costs.length][0], dp[costs.length][1]), dp[costs.length][2]);
    }

}
​