here are a row of

nhouses, 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

`cost matrix. For example,`

nx3`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

nhouses, each house can be painted with one of thekcolors. 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

`cost matrix. For example,`

nxk`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 inO(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; } };