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