Giả sử chúng ta có n ngôi nhà liên tiếp, bây giờ mỗi ngôi nhà có thể được sơn một trong k màu. Chi phí sơn của mỗi ngôi nhà với một màu nhất định là khác nhau. Bây giờ chúng ta phải ghi nhớ rằng chúng ta phải sơn tất cả các ngôi nhà sao cho không có hai ngôi nhà liền kề có màu giống nhau.
Chi phí sơn mỗi ngôi nhà với một màu nhất định được biểu diễn bằng ma trận bậc n x k. Và chúng tôi phải tìm ra chi phí tối thiểu để sơn tất cả các ngôi nhà.
Vì vậy, nếu đầu vào giống như
| 1 | 5 | 3 |
| 2 | 9 | 4 |
thì đầu ra sẽ là 5, như sơn nhà 0 thành màu 0, sơn nhà 1 thành màu 2. Khi đó chi phí tối thiểu là 1 + 4 =5; Hoặc sơn nhà 0 thành màu 2, sơn nhà 1 thành màu 0. Chi phí tối thiểu là 3 + 2 =5.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước hàng của chi phí
-
m:=(nếu n khác 0 thì kích thước col của chi phí, ngược lại là 0)
-
ret:=inf
-
để khởi tạo i:=1, khi i
-
yêu cầu:=inf
-
Xác định một mảng có kích thước m
-
Xác định rmins mảng có kích thước m
-
lmins [0]:=chi phí [i - 1, 0]
-
rmins [m - 1] =chi phí [i - 1, m - 1]
-
để khởi tạo j:=1, khi j
-
lmins [j]:=tối thiểu chi phí [i - 1, j] và lmins [j - 1]
-
-
để khởi tạo j:=m - 2, khi j> =0, cập nhật (giảm j đi 1), thực hiện -
-
rmins [j]:=tối thiểu chi phí [i - 1, j] và rmins [j + 1]
-
-
để khởi tạo j:=0, khi j
-
left:=(nếu j - 1> =0, thì lmins [j - 1], ngược lại là inf)
-
right:=(nếu j + 1
-
chi phí [i, j]:=chi phí [i, j] + min (trái, phải)
-
-
-
để khởi tạo i:=0, khi i
-
ret:=tối thiểu ret và chi phí [n - 1, i]
-
-
return (nếu ret giống với inf thì 0, nếu không thì ret)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
{{1,5,3},{2,9,4}} Đầu ra
5