首页 > 代码库 > 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