There 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.
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if (costs.empty()) return ;
for (int i = ; i < costs.size(); ++i) {
for (int j = ; j < ; ++j) {
costs[i][j] += min(costs[i-][(j+)%], costs[i-][(j+)%]);
}
}
return min(costs.back()[], min(costs.back()[], costs.back()[]));
}
};
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?
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty() || costs[].empty()) return ;
int n = costs.size(), k = costs[].size();
vector<int> min1(k), min2(k);
for (int i = ; i < costs.size(); ++i) {
min1[] = INT_MAX;
for (int j = ; j < k; ++j) {
min1[j] = min(min1[j-], costs[i-][j-]);
}
min2[k-] = INT_MAX;
for (int j = k - ; j >= ; --j) {
min2[j] = min(min2[j+], costs[i-][j+]);
}
for (int j = ; j < k; ++j) {
costs[i][j] += min(min1[j], min2[j]);
}
}
int res = INT_MAX;
for (auto c : costs.back()) {
res = min(res, c);
}
return res;
}
};
快速找到数组中去掉某个元素的最小值方法：定义两个数组，min1[i]与min2[i]分别记录从左向右到第i位与从右向左到第i位的区间最小值，那么去掉第i位的最小值就是min(min1[i], min2[i])。