数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++实现房屋粉刷 II
假设我们有一排n栋房屋，每栋房屋都可以粉刷成k种颜色之一。每栋房屋粉刷成某种颜色的成本不同。我们需要粉刷所有房屋，并且相邻房屋的颜色不能相同。
每栋房屋粉刷成某种颜色的成本由一个n x k阶矩阵表示。我们需要找到粉刷所有房屋的最小成本。
例如，如果输入为：
| 1 | 5 | 3 |
| 2 | 9 | 4 |
则输出为5，因为将房屋0粉刷成颜色0，将房屋1粉刷成颜色2。最小成本为1 + 4 = 5；或者将房屋0粉刷成颜色2，将房屋1粉刷成颜色0。最小成本为3 + 2 = 5。
为了解决这个问题，我们将遵循以下步骤：
n := costs矩阵的行数
m := (如果n非零，则为costs矩阵的列数，否则为0)
ret := inf (无限大)
for i := 1 to n-1 do −
req := inf (无限大)
定义一个大小为m的数组lmins
定义一个大小为m的数组rmins
lmins[0] := costs[i - 1, 0]
rmins[m - 1] = costs[i - 1, m - 1]
for j := 1 to m-1 do −
lmins[j] := min(costs[i - 1, j], lmins[j - 1])
for j := m - 2 down to 0 do −
rmins[j] := min(costs[i - 1, j], rmins[j + 1])
for j := 0 to m-1 do −
left := (if j - 1 >= 0, then lmins[j - 1], otherwise inf)
right := (if j + 1 < m, then rmins[j + 1], otherwise inf)
costs[i, j] := costs[i, j] + min(left, right)
for i := 0 to m-1 do −
ret := min(ret, costs[n - 1, i])
return (if ret == inf, then 0, otherwise ret)
示例
让我们来看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
int n = costs.size();
int m = n ? costs[0].size() : 0;
int ret = INT_MAX;
for (int i = 1; i < n; i++) {
int req = INT_MAX;
vector<int> lmins(m);
vector<int> rmins(m);
lmins[0] = costs[i - 1][0];
rmins[m - 1] = costs[i - 1][m - 1];
for (int j = 1; j < m; j++) {
lmins[j] = min(costs[i - 1][j], lmins[j - 1]);
}
for (int j = m - 2; j >= 0; j--) {
rmins[j] = min(costs[i - 1][j], rmins[j + 1]);
}
for (int j = 0; j < m; j++) {
int left = j - 1 >= 0 ? lmins[j - 1] : INT_MAX;
int right = j + 1 < m ? rmins[j + 1] : INT_MAX;
costs[i][j] += min(left, right);
}
}
for (int i = 0; i < m; i++) {
ret = min(ret, costs[n - 1][i]);
}
return ret == INT_MAX ? 0 : ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,5,3},{2,9,4}};
cout <<(ob.minCostII(v));
}输入
{{1,5,3},{2,9,4}}输出
5
342 次浏览
