मान लीजिए हमारे पास n गुब्बारे हैं, ये 0 से n-1 तक अनुक्रमित हैं। यहां प्रत्येक गुब्बारे पर एक संख्या चित्रित है जिसे nums नामक एक सरणी द्वारा दर्शाया गया है। हमें सभी गुब्बारों को फोड़ना है। यदि हम गुब्बारा i फोड़ते हैं तो हमें nums[i - 1] * nums[i] * nums[i + 1] संख्या के सिक्के मिलेंगे। फोड़ने के बाद, i - 1 और i + 1 फिर से आसन्न हो जाते हैं। हमें गुब्बारों को बुद्धिमानी से फोड़कर एकत्र किए जा सकने वाले अधिकतम सिक्के ढूंढने हैं।
तो यदि इनपुट [3,1,5,7] जैसा है, तो परिणाम 148 होगा। प्रारंभ में सरणी [3,1,5,7] जैसी है, फिर 1 को फोड़ने के बाद, हमें 3 * 1 * 5 = 15 मिलेगा, फिर सरणी [3,5,7] है, फिर 5 फोड़ें, तो हमें (3 * 5 * 7) = 105 मिलेगा, फिर सरणी [3,7] जैसी है, फिर 3 फोड़ें, तो हमें (1*3*7) = 21 मिलेगा, अंत में सरणी [7] है, इसलिए फोड़ने के बाद, हमें 7 मिलेगा, इसलिए कुल 15 + 105 + 21 + 7 = 148 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
n := a का आकार
यदि (n शून्येतर है) असत्य है, तो,
0 लौटाएं
क्रम n x n की एक 2D सरणी dp परिभाषित करें
l := n - 1 से आरंभ करें, जब l >= 0, l को 1 से घटाएं करें -
r := l से आरंभ करें, जब r < n, r को 1 से बढ़ाएं करें -
i := l से आरंभ करें, जब i <= r, i को 1 से बढ़ाएं करें -
y := dp[i + 1, r] यदि i + 1 < n, अन्यथा 0
z := a[l - 1] यदि l - 1 >= 0 अन्यथा 1
w := a[r + 1] यदि r + 1 < n अन्यथा 1
x := dp[l, i - 1] यदि i - 1 >= 0, अन्यथा 0 + y + (z * w * a[i])
dp[l, r] := dp[l, r] और x का अधिकतम
dp[0, n - 1] लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxCoins(vector<int>& a) { int n = a.size(); if(!n)return 0; vector < vector <int>> dp(n,vector <int> (n)); for(int l = n-1;l>=0;l--){ for(int r=l;r<n;r++){ for(int i =l;i<=r;i++){ dp[l][r] = max(dp[l][r],(i-1>=0?dp[l][i-1]:0) +(i+1<n?dp[i+1][r]:0)+((l-1>=0?a[l-1]:1 )*(r+1<n?a[r+1]:1)*a[i])); } } } return dp[0][n-1]; } }; main(){ Solution ob; vector<int> v = {3,1,5,7}; cout << (ob.maxCoins(v)); }इनपुट
[3,1,5,7]
आउटपुट
148
