मान लीजिए हमारे पास एक पंक्ति में 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 := costs का पंक्ति आकार
m := (यदि n शून्येतर है, तो costs का स्तंभ आकार, अन्यथा 0)
ret := inf
i := 1 से आरंभ करें, जब i <n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
req := inf
आकार m का एक ऐरे lmins परिभाषित करें
आकार m का एक ऐरे rmins परिभाषित करें
lmins[0] := costs[i - 1, 0]
rmins[m - 1] = costs[i - 1, m - 1]
j := 1 से आरंभ करें, जब j < m, अद्यतन करें (j को 1 से बढ़ाएं), करें −
lmins[j] := costs[i - 1, j] और lmins[j - 1] का न्यूनतम
j := m - 2 से आरंभ करें, जब j >= 0, अद्यतन करें (j को 1 से घटाएं), करें −
rmins[j] := costs[i - 1, j] और rmins[j + 1] का न्यूनतम
j := 0 से आरंभ करें, जब j < m, अद्यतन करें (j को 1 से बढ़ाएं), करें −
left := (यदि j - 1 >= 0, तो lmins[j - 1], अन्यथा inf)
right := (यदि j + 1 < m, तो rmins[j + 1], अन्यथा inf)
costs[i, j] := costs[i, j] + min(left, right)
i := 0 से आरंभ करें, जब i < m, अद्यतन करें (i को 1 से बढ़ाएं), करें −
ret := ret और costs[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
