题目描述

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.

Note:
All costs are positive integers.

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

样例

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
             Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. 

算法1

DP $O(n * k)$

C++ 代码

    // f[i][j]: 用颜色j刷第i个house的最小cost
    // f[i][j] = min { f[i-1][k] | k!=j } + c[i][j]
    // 时间复杂度是 O(n * k^2)，可化简到 O(n * k)

    // 当处理 house i 时，只需要知道 i-1的最小值和次小值，以及最小值的漆的颜色，不需要遍历所有颜色k
    // 所以不需要开2维数组，只要 记录 min1, min2, min1_index 即可

    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n==0) return 0;

        int k = costs[0].size();

        int min1 = INT_MAX, min2 = INT_MAX, min1_index=-1;

        for(int j=0; j<k; j++) {
            if(costs[0][j] < min1) { min2 = min1; min1 = costs[0][j]; min1_index = j; }
            else if(costs[0][j] < min2) { min2 = costs[0][j]; }
        }

        for(int i=1; i<n; i++) {
            int min1_ = INT_MAX, min2_ = INT_MAX, min1_index_=-1;
            for(int j=0; j<k; j++) {
                int cost = costs[i][j] + (min1_index==j? min2 : min1);

                if(cost < min1_) { 
                    min2_=min1_; 
                    min1_ = cost;
                    min1_index_ = j; 
                }
                else if (cost < min2_) {
                    min2_ = cost; 
                }
            }
            min1 = min1_;
            min2 = min2_; 
            min1_index = min1_index_;
        }

        return min1;
    }