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 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.

代码

// time： o(n)   space: o(1)

思路

道很明显的动态规划的题目. 每个房子有三种染色方案, 那么如果当前房子染红色的话, 最小代价将是上一个房子的绿色和蓝色的最小代价+当前房子染红色的代价. 对另外两种颜色也是如此. 因此动态转移方程为:

         dp\[i\]\[0\] = min\(dp\[i-1\]\[1\], dp\[i-1\]\[2\]\) + costs\[i-1\]\[0\];

         dp\[i\]\[1\] = min\(dp\[i-1\]\[0\], dp\[i-1\]\[2\]\) + costs\[i-1\]\[1\];

         dp\[i\]\[2\] = min\(dp\[i-1\]\[0\], dp\[i-1\]\[1\]\) + costs\[i-1\]\[2\];

find the minimum cost to paint the houses up to current house in red, blue or green.

代码

//Space O(1) Time O(n)
class Solution {
    public int minCost(int[][] costs) {
        if(costs == null || costs[0].length ==0) return 0;
        for(int i = 1; i<costs.length; i++){
            costs[i][0] += Math.min(cost[i-1][1],cost[i-1][2]);
            costs[i][1] += Math.min(cost[i-1][0],cost[i-1][2]);
            costs[i][2] += Math.min(cost[i-1][0],cost[i-1][1]);
        }
        int n = costs.length - 1;
        return Math.min(Math.min(costs[n][0],costs[n][1],costs[n][2]))
    }
}