516. 房屋染色 II
这里有
n
个房子在一列直线上，现在我们需要给房屋染色，共有
k
种颜色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。
费用通过一个
n
x
k
的矩阵给出，比如
cost[0][0]
表示房屋
0
染颜色
0
的费用，
cost[1][2]
表示房屋
1
染颜色
2
的费用。
样例
样例1
输入:
costs = [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
说明:
三个屋子分别使用第1,2,1种颜色，总花费是10。
样例2
输入:
costs = [[5]]
输出: 5
说明：
只有一种颜色，一个房子，花费为5
挑战
用O(nk)的时间复杂度解决
注意事项
所有费用都是正整数
public class Solution {
/**
* @param costs: n x k cost matrix
* @return: an integer, the minimum cost to paint all houses
*/
public int minCostII(int[][] costs) {
// write your code here
if (costs.length == 0) return 0;
for (int i = 0; i < costs.length-1; i++) {
int flag=0;
int min = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for (int j = 0; j < costs[i].length; j++) {
if (costs[i][j] < min) {
min2=min;
min = costs[i][j];
flag=j;
}else if(costs[i][j] < min2){
min2=costs[i][j];
}
}
for (int k = 0; k < costs[i].length; k++) {
if (flag == k) {
costs[i+1][k] = costs[i+1][k]+min2;
} else {
costs[i+1][k] = costs[i+1][k]+min;
}
}
}
int ret = costs[costs.length - 1][0];
for (int i = 1; i < costs[costs.length - 1].length ; i++) {
ret=Math.min(ret, costs[costs.length - 1][i]);
}
return ret;
}
}