2015年9月10日星期四

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:

public class Solution {
    public int minCost(int[][] costs) {
        int house = costs.length;
        if (house == 0) return 0;
        int red[] = new int[house];
        int blue[] = new int[house];
        int green[] = new int[house];
     
        red[0] = costs[0][0];
        blue[0] = costs[0][1];
        green[0] = costs[0][2];
     
        for (int i = 1; i < house; i++) {
            red[i] = Math.min(blue[i - 1], green[i - 1]) + costs[i][0];
            blue[i] = Math.min(red[i - 1], green[i - 1]) + costs[i][1];
            green[i] = Math.min(red[i - 1], blue[i - 1]) + costs[i][2];
        }
     
        return Math.min(Math.min(red[house - 1], blue[house - 1]), green[house - 1]);
    }
}

=======

public class Solution {
    public int minCost(int[][] costs) {
        int house = costs.length;
        if (house == 0) return 0;
       
        int r = costs[0][0];
        int b = costs[0][1];
        int g = costs[0][2];
       
        for (int i = 1; i < house; i++) {
            int rr = r;
            int bb = b;
            int gg = g;
            r = Math.min(bb, gg) + costs[i][0];
            b = Math.min(rr, gg) + costs[i][1];
            g = Math.min(rr, bb) + costs[i][2];
        }
       
        return Math.min(Math.min(r, b), g);
    }
}

没有评论:

发表评论