假设我们连续有n座房屋，现在每座房屋都可以用k种颜色之一绘制。具有某种颜色的每个房屋的绘画成本是不同的。现在我们要记住，我们必须对所有房屋进行粉刷，以使两个相邻的房屋都没有相同的颜色。
用nx k阶矩阵表示用某种颜色粉刷每所房屋的成本。而且，我们必须找到粉刷所有房屋的最低成本。
所以，如果输入像
| 1 | 5 | 3 |
| 2 | 9 | 4 |
则输出为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