265. Paint House II

题目：
There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix. For example, costs0 is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

解答：
利用paint house的思路，只不过把三种颜色换成了k种颜色，所以：

//State: f[i][j] is the minimum cost of painting i houses with color j
//Function: f[i][j] = Math.min(f[i - 1][k(except j)]) + costs[i][j];
//Initialize: f[0][j] = costs[0][j];
//Result: Math.min(f[costs.length - 1][j]);
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int house = costs.length, color = costs[0].length;
int[][] f = new int[house][color];
for (int i = 0; i
followup是如何把它的复杂度降到o(nk), 那么就是如果将颜色的部分只扫一遍。参考leetcode的discuss里most voted answer, 只需要记录下每个house的最小的两个颜色。如果下一个颜色跟这个颜色不一样，就取最小的这个颜色加上这次所选的颜色，并找出最小值；如果下一个颜色跟这个颜色一样，那么我们不可以取最小的这个颜色，所以我们取第二小的颜色加上这次所选的颜色。最后把最小的颜色输出就可以了。

//Only the first two minimum costs count, so we keep track on min1 and min2 for each house
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}

    int house = costs.length, color = costs[0].length;    int min1 = -1, min2 = -1;    for (int i = 0; i 

关键字：leetcode, 算法, java, costs

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！