首页 > 代码库 > 256. Paint House

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

看了discussion大神的解法,思路无比清晰。每次paint我们都有三种选择,红蓝绿,那么总的cost就是现在的选择加上之前不同于现在选择的总cost。最后得出三种选择的总cost,比较得出最小值就是所需要的。觉得吧,还是需要看这种能提供清晰思路的解法,能使自己的思路也更加清晰,才能引导自己。

ref:https://discuss.leetcode.com/topic/32408/share-my-very-simple-java-solution-with-explanation

public class Solution {    public int minCost(int[][] costs) {    if(costs.length==0) return 0;    int prevR= costs[0][0];    int prevG = costs[0][1];    int prevB = costs[0][2];    for(int i=1; i<costs.length; i++){        int curR = Math.min(prevG,prevB)+costs[i][0];        int curG = Math.min(prevR,prevB)+costs[i][1];        int curB = Math.min(prevR,prevG)+costs[i][2];        prevR = curR;        prevG = curG;        prevB = curB;    }    return Math.min(Math.min(prevR,prevG),prevB);    }}

 

256. Paint House