粉刷房子
题目
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.
有n间房子,每间房子可以被涂成以下三种颜色之一:红色,蓝色和绿色.用不同的颜色粉刷房子产生的费用是不同的,你必须要将所有的房子都粉刷同时相邻的房子颜色不能一样.
用某种颜色来粉刷每所房子的成本用一个n*3的矩阵来表示.例如,[0][0]是使用红颜色粉刷房子0的成本,[1][2]是使用绿色粉刷房子1的成本,以此类推.找出粉刷所有房子最小的花费.
提示:
所有的花费都是正数.
思路
还是使用动态规划,但是题目有点不好理解.意思其实是这样的.给定一个二维数组,int[][] costs,第一位就是当前在哪个房子,第二位有三个数字,不一定是0,1,2,也有可能是2,4,6,所以给的数组可能是[[0,1,2],[1,3,2],[1,1,2]],这个时候要选出房子粉刷使用的最小值.
下面的代码是从第二个房子开始,记录选用不同情况下的花费,然后到最后再选用每种情况里面最小的值.
代码
public int minCost(int[][] costs) {
if(costs == null || costs.length == 0){
return 0;
}
for(int i = 1;i < costs.length;i++){
costs[i][0] +=Math.min(costs[i-1][1],costs[i-1][2]);
costs[i][1] +=Math.min(costs[i-1][0],costs[i-1][2]);
costs[i][2] +=Math.min(costs[i-1][1],costs[i-1][0]);
}
int m = costs.length-1;
return Math.min(Math.min(costs[m][1],costs[m][2]),costs[m][0]);
}
