C ++中的Paint House II
假设我们连续有n座房屋，现在每座房屋都可以用k种颜色之一绘制。具有某种颜色的每个房屋的绘画成本是不同的。现在我们要记住，我们必须对所有房屋进行粉刷，以使两个相邻的房屋都没有相同的颜色。
用nxk阶矩阵表示用某种颜色粉刷每所房屋的成本。而且，我们必须找到粉刷所有房屋的最低成本。
所以，如果输入像
则输出为5，将油漆房0变为颜色0，将油漆房1变为颜色2。则最小成本为1+4=5；或将房屋0涂成颜色2，将房屋1涂成颜色0。最低成本为3+2=5。
为了解决这个问题，我们将遵循以下步骤-
n：=成本行大小
m：=（如果n不为零，则表示成本的col大小，否则为0）
ret：=inf
对于初始化i：=1，当i<n时，更新（将i增加1），-
左：=（如果j-1>=0，则为lmins[j-1]，否则为inf）
右：=（如果j+1<m，则rmins[j+1]，否则inf）
成本[i，j]：=成本[i，j]+分钟（左，右）
rmins[j]：=成本[i-1，j]和rmins[j+1]的最小值
lmins[j]：=成本[i-1，j]和lmins[j-1]的最小值
要求：=inf
定义大小为m的数组lmins
定义大小为m的数组rmins
lmins[0]：=费用[i-1，0]
rmins[m-1]=费用[i-1，m-1]
对于初始化j：=1，当j<m时，更新（将j增加1），-
对于初始化j：=m-2，当j>=0时，更新（将j减1），执行-
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
对于初始化i：=0，当i<m时，更新（将i增加1），执行-
ret：=最小的ret和成本[n-1，i]
返回（如果ret与inf相同，则为0，否则为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