265. Paint House II

Leetcode Dynamic Programming

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, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

All costs are positive integers.

Example:

Given n = 3, k = 3, costs = [[14,2,11],[11,14,5],[14,3,10]] 
return 10. 
Explanation: house 0 is color 2, house 1 is color 3, 
             house 2 is color 2, 2 + 5 + 3 = 10

ChallengeCould: you solve it in $O(nk)$?

分析

这道题目LeetCode要收费的，相应的LintCode链接。与LeetCode 256. Paint House一摸一样，把3变成$k$而已。代码思路一摸一样。

public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0) return 0;
    int[][] dp = costs.clone();
    int k = dp[0].length;
    int prevMin = Integer.MAX_VALUE;
    for (int i = 1; i < dp.length; i++)
        for (int j = 0; j < k; j++) {
            // 求刷到前一栋房子的最小费用为prevMin
            // 注意每个j对应的prevMin都不一样
            prevMin = Integer.MAX_VALUE;
            for (int kk = 1; kk < k; kk++)
                if (dp[i - 1][(j + kk) % k] < prevMin)
                    prevMin = dp[i - 1][(j + kk) % k];
            // 刷到第i栋房子，用j颜色的费用 = 
            // 求刷到前一栋房子i-1的最小费用 + 刷这一栋房子i的费用
            dp[i][j] += prevMin;
        }

    // 求刷到最后一栋房子的最小费用
    prevMin = Integer.MAX_VALUE;
    for (int kk = 0; kk < k; kk++)
        if (dp[dp.length - 1][kk] < prevMin)
            prevMin = dp[dp.length - 1][kk];
    return prevMin;
}

上面的代码可读性很差，尤其是下标的求余操作，把它封装成函数之后，不仅可读性增加了，而且执行速度也增加了：

/**
 * @param costs: n x k cost matrix
 * @return: an integer, the minimum cost to paint all houses
 */
public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0) return 0;
    int[][] dp = costs.clone();
    int k = dp[0].length;
    int prevMin = Integer.MAX_VALUE;
    for (int i = 1; i < dp.length; i++)
        for (int j = 0; j < k; j++) {
            // 刷到第i栋房子，用j颜色的费用 = 
            // 求刷到前一栋房子i-1的最小费用 + 刷这一栋房子i的费用
            dp[i][j] += minExpense(dp[i - 1], j);
        }  
    return minExpense(dp[dp.length - 1], -1);
}

/**
 * 求刷到前一栋房子的最小费用
 * @param nums: 费用
 * @param exclusive: 当前房子的颜色，被排除在前一栋房子的颜色中
 * @return: 刷到前一栋房子的最小费用
 */
private int minExpense(int[] nums, int exclusive) {
    int min = Integer.MAX_VALUE;
    for (int k = 0; k < nums.length; k++)
        if (k != exclusive && nums[k] < min)
            min = nums[k];
    return min;
}