here are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

// dp0[i] stores the minimum cost for painting i houses that the ith house should be printed with red
// dp1[i] stores the minimum cost for painting i houses that the ith house should be printed with blue
// dp2[i] stores the minimum cost for painting i houses that the ith house should be printed with green
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int len = costs.size();
        if(len == 0) return 0;
        int dp0[len], dp1[len], dp2[len];
        dp0[0] = costs[0][0];
        dp1[0] = costs[0][1];
        dp2[0] = costs[0][2];
        for(int i = 1; i < costs.size(); i++){
            dp0[i] = min(dp1[i - 1], dp2[i - 1]) + costs[i][0];
            dp1[i] = min(dp0[i - 1], dp2[i - 1]) + costs[i][1];
            dp2[i] = min(dp1[i - 1], dp0[i - 1]) + costs[i][2];
        }
        return min(dp0[len - 1], min(dp1[len - 1], dp2[len - 1]));
    }
};

Paint House II

here 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?

O(nk^2) Solution

class Solution {
public:
    int MAX_INT = 0x7fffffff;
    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;
        int dp[n][k];
        for(int i = 0; i < k; i++){
            dp[0][i] = costs[0][i];
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < k; j++){
                int minCost = MAX_INT;
                for(int l = 0; l < k; l++){
                    if(l == j) continue;
                    minCost = dp[i - 1][l] < minCost? dp[i - 1][l]: minCost;
                }
                dp[i][j] = minCost + costs[i][j];
            }
        }
        int ans = MAX_INT;
        for(int i = 0; i < k; i++){
            ans = dp[n - 1][i] < ans? dp[n - 1][i]: ans;
        }
        return ans;
    }
};

O(nk) solution

The original bottleneck is the calculation of minCost of dp[i – 1][l], which hinders the performance.

This new solution stores 2 minimum costs in dp[i – 1][1~k]. There is no need to calculate it again and again which is a waste of time.

class Solution {
public:
    int MAX_INT = 0x7fffffff;
    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;
        int dp[n][k];
        for(int i = 0; i < k; i++){
            dp[0][i] = costs[0][i];
        }
        for(int i = 1; i < n; i++){
            int minCosts[2];
            minCosts[0] = MAX_INT;
            minCosts[1] = MAX_INT;
            for(int j = 0; j < k; j++){
                if(dp[i - 1][j] <= minCosts[0]){
                    minCosts[1] = minCosts[0];
                    minCosts[0] = dp[i - 1][j];
                }
                else if(dp[i - 1][j] <= minCosts[1]){
                    minCosts[1] = dp[i - 1][j];
                }
            }
            for(int j = 0; j < k; j++){
                int minCost = minCosts[0];
                if(dp[i - 1][j] == minCost){
                    minCost = minCosts[1];
                }
                dp[i][j] = minCost + costs[i][j];
            }
        }
        int ans = MAX_INT;
        for(int i = 0; i < k; i++){
            ans = dp[n - 1][i] < ans? dp[n - 1][i]: ans;
        }
        return ans;
    }
};