ধরুন আমাদের 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], তারপরে burst 5, তাই আমরা পাব (3 * 5 * 7) =105, তারপর অ্যারে হল [3,7] এর মত, তারপরে 3 বার্স্ট, তাই আমরা পাবে (1*3*7) =21, অবশেষে অ্যারে হল [7], তাই বার্স্ট করার পরে, আমরা 7 পাব, তাই মোট হল 15 + 105 + 21 + 7 =148।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=a
এর আকার -
যদি (n অ-শূন্য) মিথ্যা হয়, তাহলে,
-
রিটার্ন 0
-
-
একটি 2D অ্যারে ডিপি অর্ডার n x n
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য l :=n - 1, যখন l>=0, l কমিয়ে 1 do −
-
আরম্ভ করার জন্য r :=l, যখন r
-
শুরু করার জন্য i :=l, যখন i <=r, i 1 do −
দ্বারা বাড়ান-
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
-
-
-
-
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
