n개의 집이 연속으로 있다고 가정하면 이제 각 집은 k 색상 중 하나로 칠할 수 있습니다. 특정 색상의 집마다 페인트 비용이 다릅니다. 이제 우리는 인접한 두 집이 같은 색을 가지지 않도록 모든 집을 페인트해야 한다는 것을 명심해야 합니다.
각 집을 특정 색상으로 칠하는 비용은 n x k 차수의 행렬로 표시됩니다. 그리고 우리는 모든 집을 페인트하는 데 필요한 최소 비용을 찾아야 합니다.
따라서 입력이 다음과 같으면
| 1 | 5 | 3 |
| 2 | 9 | 4 |
그러면 페인트 하우스 0은 색상 0으로, 페인트 하우스 1은 색상 2로 출력되므로 출력은 5가 됩니다. 그러면 최소 비용은 1 + 4 =5입니다. 또는 하우스 0을 색상 2로, 하우스 1을 색상 0으로 페인트합니다. 최소 비용은 3 + 2 =5입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=비용의 행 크기
-
m :=(n이 0이 아니면 비용의 열 크기, 그렇지 않으면 0)
-
ret :=inf
-
initialize i :=1의 경우, i
를 수행합니다. -
요청 :=정보
-
m
크기의 배열 lmin을 정의합니다. -
m
크기의 배열 rmin을 정의하십시오. -
lmins[0] :=비용[i - 1, 0]
-
rmins[m - 1] =비용[i - 1, m - 1]
-
initialize j :=1의 경우 j
-
lmins[j] :=최소 비용[i - 1, j] 및 lmins[j - 1]
-
-
초기화 j :=m - 2의 경우 j>=0일 때 업데이트(j를 1만큼 감소), −
-
rmins[j] :=최소 비용[i - 1, j] 및 rmins[j + 1]
-
-
j 초기화의 경우:=0, j
-
왼쪽 :=(j - 1>=0이면 lmins[j - 1], 그렇지 않으면 inf)
-
right :=(j + 1
-
비용[i, j] :=비용[i, j] + min(왼쪽, 오른쪽)
-
-
-
initialize i :=0의 경우, i
-
ret :=ret 및 비용의 최소값[n - 1, i]
-
-
return (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