ধরুন আমাদের একটি সারিতে n ঘর আছে, এখন প্রতিটি ঘর k রঙের একটি দিয়ে আঁকা যেতে পারে। একটি নির্দিষ্ট রঙ দিয়ে প্রতিটি বাড়ির পেইন্টিং খরচ আলাদা। এখন আমাদের মনে রাখতে হবে যে আমাদের সমস্ত ঘরকে এমনভাবে রঙ করতে হবে যাতে কোনও দুটি সংলগ্ন বাড়ির রঙ একই রকম না হয়৷
একটি নির্দিষ্ট রঙ দিয়ে প্রতিটি ঘর আঁকার খরচ n x 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
-
req :=inf
-
m
আকারের একটি অ্যারে lmins সংজ্ঞায়িত করুন -
m
আকারের একটি অ্যারে rmins সংজ্ঞায়িত করুন -
lmins[0] :=খরচ[i - 1, 0]
-
rmins[m - 1] =খরচ[i - 1, m - 1]
-
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)
-
ডান :=(যদি j + 1
-
খরচ[i, j] :=খরচ[i, j] + মিনিট(বাম, ডান)
-
-
-
আরম্ভ করার জন্য i :=0, যখন i
-
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
