Paint House

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.

时间复杂度 o(n)，空间复杂度o(1);

class Solution {
    public int minCost(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0].length == 0)
            return 0;
        
        int res = Integer.MAX_VALUE;
        
        for(int i = 1; i < costs.length ; i++){
            costs[i][0] = costs[i][0] + Math.min(costs[i-1][1],costs[i-1][2]);
            costs[i][1] = costs[i][1] + Math.min(costs[i-1][2],costs[i-1][0]);
            costs[i][2] = costs[i][2] + Math.min(costs[i-1][1],costs[i-1][0]);
        }
        
        for(int j = 0; j < 3;j++){
            res = Math.min(res, costs[costs.length-1][j]);
        }
        
        return res;
        
    }
}

dp问题，尝试在当前状况下，考虑上一个状况对现在的影响，比如这个题，现在状况下每一种颜色的花费，其实是由上一个状况时另外两种不同颜色的花费的最小值和现在颜色的花费的和决定的，上一个的这个最小值又是由上上一个状况决定的，以此类推的来解决dp问题

https://leetcode.com/problems/paint-house/discuss/170419/Java-DP-Solution-O(n)-with-Explanation