मान लीजिए कि हमारे पास n गुब्बारे हैं, ये 0 से n-1 तक अनुक्रमित हैं। यहां प्रत्येक गुब्बारे को एक संख्या के साथ चित्रित किया जाता है जिसे एक सरणी द्वारा दर्शाया जाता है जिसे अंक कहा जाता है। हमें सारे गुब्बारे फोड़ने हैं। यदि हम गुब्बारा फोड़ते हैं तो हमें अंक [i - 1] * अंक [i] * अंक [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 :=आकार का
-
अगर (n गैर-शून्य है) गलत है, तो,
-
वापसी 0
-
-
क्रम n x n के एक 2D सरणी dp को परिभाषित करें
-
शुरू करने के लिए l :=n-1, जब l>=0, l को 1 से घटाएं -
-
r :=l को इनिशियलाइज़ करने के लिए, जब r
-
i :=l को इनिशियलाइज़ करने के लिए, जब i <=r, i को 1 से बढ़ाएँ -
-
y :=dp[i + 1, r] अगर i + 1
-
z :=a[l - 1] अगर l - 1>=0 अन्यथा 1
-
w :=a[r + 1] यदि r + 1
-
x :=dp[l, i - 1] अगर i - 1> =0, अन्यथा 0 + y + (z * w * a[i])
-
dp[l, r] :=अधिकतम dp[l, r] और x
-
-
-
-
वापसी डीपी [0, एन -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