मान लीजिए कि हमारे पास एक पंक्ति में 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 शून्य नहीं है, तो लागत का कुल आकार, अन्यथा 0)
-
रिट :=inf
-
इनिशियलाइज़ i :=1 के लिए, जब i
-
अनुरोध :=inf
-
आकार m
. के एक सरणी lmins को परिभाषित करें -
m
. आकार की एक सरणी rmins परिभाषित करें -
एलमिन्स[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] + मिनट (बाएं, दाएं)
-
-
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i
-
ret :=न्यूनतम रिट और लागत [n - 1, i]
-
-
वापसी (यदि रिट inf के समान है, तो 0, अन्यथा रिट)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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