Paint House II

题目描述

n个房间排成一行，现在需要将每个房间都染色，相邻的房间不能使用同一种颜色。共有 k 种颜色可供选择，对每个房间而言使用每种颜色的花费不同。

注意： 所有的花费都是正整数。

Example：

costs = [
  [14,2,11],
  [11,14,5],
  [14,3,10]
]

costs[i][j] 表示给第 i 个房间染成第 j 种颜色的花费（i, j 从 0 编号）。 返回10， 第 0 个房间使用第 2 种颜色， 第 1 个房间使用第 3 种颜色，第 2 个房间使用第 2 个颜色。所以有 2 + 5 + 3 = 10。

题目链接

分析解答

本题中，对于第 i （0 <= i < n）个房间有 k 种不同的染色方案，如果将第 i 个房间染成了第 j 种颜色，那么第 i - 1 个房间一定不能使用第 j 种颜色，设 dp[i][j] = 将前 i 个房间染色完成后，且第 i 个房间使用了第 j 种颜色 所需的总花费。 那么可以得到递推公式为： dp[i][j] = min{dp[i - 1][t], 0 <= t < k 且 t != j}. 我们可以枚举每个房间和将该房间染成的颜色，这需要 $$O(n \times k)$$ 的时间（n 是房间数，k 是颜色数），之后我们需要知道将前 i - 1个房间染色完成后 且第 i - 1 个房间没有使用和第 i 个房间相同颜色 所需要的总花费，这需要 O(k) 的时间，所以总的时间复杂度就是 $$O(n \times k^2)$$, 但是该算法无法全部通过本题的测试数据，所以时间复杂度偏高。

• dp的题目我们以前做了一个总结就是按照下面四步来说会特别清楚。 比如这道题上面的可以这么列出来，下面改进的 方法你也可以这么来写
• state:dp[i][j]表示将前 i 个房间染色完成后，且第 i 个房间使用了第 j 种颜色 所需的总花费
• function: dp[i][j] = min{dp[i - 1][t], 0 <= t < k 且 t != j}
• initialize: 初始化dp[0][j] 第一个房子染成颜色j的花费
• answer: 结果dp[n-1][j] 中的最大值

我们发现，很多时间都用在 寻找将前 i - 1个房间染色完成后 且第 i - 1 个房间没有使用和第 i 个房间相同颜色 所需要的总花费。我们做了很多重复的工作，其实这可以高效的预处理出来。在将前 i - 1 个房间染色结束之后，我们记：tmpMin[j] = min{dp[i - 1][t], 0 <= t < k 且 t != j }。也就是说 tmpMin[j] 代表第 i - 1 个房间使用除第 j 种颜色以外的颜色可以获得的最小花费。为了得到 tmpMin[j]，只需要从前往后，从后往前分别扫一遍 dp[i - 1][j] 即可得到。具体做法为：tmpMin[j] = min{dp[i - 1][0...j - 1], dp[i - 1][j + 1...k - 1] }，这实际上就是以第 j 个数为分界点的 前缀的最小值 和 后缀的最小值 较小的一个，从前往后扫时，维护前缀最小值；从后往前扫时，维护后缀最小值。 这样总的时间复杂度就降低到了 O(n * k)。

参考程序（动态规划）

class Solution {
public:
    /**
     * @param costs n x k cost matrix
     * @return an integer, the minimum cost to paint all houses
     */
    int minCostII(vector<vector<int>>& costs) {
        // Write your code here
        int n = costs.size();
        if (n == 0) { 
            return 0;
        }

        int k = costs[0].size();
        vector<vector<int>> dp(n, vector<int>(k, INT_MAX));
        // tmpMin[i] 表示前 j 个房子染色结束之后，且第 j 个房间使用的不是第 i 种颜色 的最小总花费。
        // 每次更新完 dp[i]， 都会重新计算 tmpMin 数组。
        vector<int> tmpMin(k, 0); 

        for (int i = 0; i < n; ++ i) {

            for (int j = 0; j < k; ++ j) {
                dp[i][j] = tmpMin[j] + costs[i][j];
                tmpMin[j] = INT_MAX;
            }
            // 计算 tmpMin 数组
            // tmp 维护 dp[i] 数组的前缀最小值
            int tmp = INT_MAX;
            for (int j = 0; j < k - 1; ++ j) {
                tmp = min(tmp, dp[i][j]);
                tmpMin[j + 1] = tmp;
            }
            // tmp 维护 dp[i] 数组的后缀最小值
            tmp = INT_MAX;
            for (int j = k - 1; j > 0; -- j) {
                tmp = min(tmp, dp[i][j]);
                tmpMin[j - 1] = min(tmpMin[j - 1], tmp);
            }
        }

        int ans = INT_MAX;
        for (int i = 0; i < k; ++ i) {
            ans = min(ans, dp[n - 1][i]);
        }
        return ans;
    }
};

面试官角度分析(optional)

此题 时间复杂度为 $$O(n \times k)$$ 的优化之后的动态规划算法可达到面试官的要求。笔者认为，一般的 $$O(n \times k^2)$$ 动态规划方法可以达到hire；优化之后的 $$O(n \times k)$$ 方法可以达到strong hire。

LintCode上的相关题目

• Paint House I
• Paint House II
• Product of Array Exclude Itself