265. Paint House II

• Difficulty: Hard

• Topics: Dynamic Programming

• Similar Questions:

  • Product of Array Except Self

  • Sliding Window Maximum

  • Paint House

  • Paint Fence

Problem:

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.

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. 

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

Solutions:

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int k = costs[0].size();
        if (k == 0) return 0;
        if (k == 1) { // check the situation when there is only one color.
            if (n == 1) return costs[0][0]; 
            return -1;
        }

        costs.push_back(vector<int>(k, 0));
        ++n;



        vector<vector<int>> dp (n + 1, vector<int>(k, 0));

        int least1 = 0;
        int color1 = -1;
        int least2 = 0;
        int color2 = -1;

        for (int i = 1; i <= n; ++i) {
            int curLeast1 = INT_MAX;
            int curColor1 = -1;
            int curLeast2 = INT_MAX;
            int curColor2 = -1;

            for (int j = 0; j < k; ++j) {
                if (j == color1) {
                    dp[i][j] = costs[i-1][j] + least2;
                } else {
                    dp[i][j] = costs[i-1][j] + least1;
                }

                if (dp[i][j] < curLeast1) {
                    curLeast2 = curLeast1;
                    curColor2 = curColor1;
                    curLeast1 = dp[i][j];
                    curColor1 = j;
                } else if (dp[i][j] < curLeast2) {
                    curLeast2 = dp[i][j];
                    curColor2 = j;
                }

            }
            cout << endl;

            least1 = curLeast1;
            color1 = curColor1;
            least2 = curLeast2;
            color2 = curColor2;

        }

        return least1;
    }
};