[LeetCode] Paint House I & II
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode] Paint House I & II，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2423字，纯文字阅读大概需要4分钟。
内容图文
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.
1
class
Solution {
2
public
:
3
int minCost(vector<vector<int>>& costs) {
4if (costs.empty()) return0;
5for (int i = 1; i < costs.size(); ++i) {
6for (int j = 0; j < 3; ++j) {
7 costs[i][j] += min(costs[i-1][(j+1)%3], costs[i-1][(j+2)%3]);
8 }
9 }
10return min(costs.back()[0], min(costs.back()[1], costs.back()[2]));
11 }
12 };
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?
1
class
Solution {
2
public
:
3
int minCostII(vector<vector<int>>& costs) {
4if (costs.empty() || costs[0].empty()) return0;
5int n = costs.size(), k = costs[0].size();
6 vector<int> min1(k), min2(k);
7for (int i = 1; i < costs.size(); ++i) {
8 min1[0] = INT_MAX;
9for (int j = 1; j < k; ++j) {
10 min1[j] = min(min1[j-1], costs[i-1][j-1]);
11 }
12 min2[k-1] = INT_MAX;
13for (int j = k - 2; j >= 0; --j) {
14 min2[j] = min(min2[j+1], costs[i-1][j+1]);
15 }
16for (int j = 0; j < k; ++j) {
17 costs[i][j] += min(min1[j], min2[j]);
18 }
19 }
20int res = INT_MAX;
21for (auto c : costs.back()) {
22 res = min(res, c);
23 }
24return res;
25 }
26 };
快速找到数组中去掉某个元素的最小值方法：定义两个数组，min1[i]与min2[i]分别记录从左向右到第i位与从右向左到第i位的区间最小值，那么去掉第i位的最小值就是min(min1[i], min2[i])。
原文：http://www.cnblogs.com/easonliu/p/4784858.html
内容总结
以上是互联网集市为您收集整理的[LeetCode] Paint House I & II全部内容，希望文章能够帮你解决[LeetCode] Paint House I & II所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。