C++ में बक्से निकालें

मान लीजिए कि हमारे पास अलग-अलग रंगों के कई बॉक्स हैं, इन रंगों को अलग-अलग सकारात्मक संख्याओं द्वारा दर्शाया गया है। हम बक्से को हटाने के लिए कई दौर का अनुभव कर सकते हैं जब तक कि कोई बॉक्स न बचा हो। प्रत्येक दौर में हम एक ही रंग के कुछ निरंतर बक्से चुन सकते हैं (के बक्से, के> =1 से बना), और उन्हें हटा दें और के * के अंक प्राप्त करें। तो अगर इनपुट इस तरह है - [1,3,2,2,2,4,4,3,1], तो आउटपुट 21 होगा।

अधिकतम अंक प्राप्त करें जो आप प्राप्त कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को हल करें () को परिभाषित करें, यह एक सरणी बॉक्स लेगा, i, j, k, एक 3D सरणी dp,
यदि i> j, तो −
- वापसी 0
यदि dp[i, j, k] -1 के बराबर नहीं है, तो −
- रिटर्न डीपी[i, j, k]
सेवानिवृत्त:=-इन्फ़
स्थिति की जांच करने के लिए i + 1 <=j और बॉक्स[i + 1] बॉक्स के समान है[i], अपडेट करें (i से 1 बढ़ाएं), (1 से k बढ़ाएं), कुछ न करें -
ret :=अधिकतम रिट और (k + 1) * (k + 1) + फ़ंक्शन को कॉल करें हल करें (बॉक्स, i + 1, j, 0, dp)
इनिशियलाइज़ x :=i + 1 के लिए, जब x <=j, अपडेट करें (x को 1 से बढ़ाएँ), −
- यदि बॉक्स[x], बक्सों के समान है[i], तो −
  - ret:=अधिकतम रिट और सॉल्व ((बॉक्स, i + 1, x - 1, 0, dp) + सॉल्व (बॉक्स, x, j, k + 1, dp))
रिटर्न डीपी[i, j, k] =ret
मुख्य विधि से, निम्न कार्य करें
n :=बक्सों का आकार
एक 3D सरणी dp को क्रम में परिभाषित करें (n + 1) x (n + 1) x (n + 1), इसे -1 से भरें
रिटर्न सॉल्व (बॉक्स, 0, n - 1, 0, dp)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int solve(vector <int>& boxes, int i, int j, int k, vector < vector < vector <int > > >& dp){
      if(i > j) return 0;
      if(dp[i][j][k] != -1) return dp[i][j][k];
      int ret = INT_MIN;
      for(; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
      ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
      for(int x = i + 1; x <= j; x++){
         if(boxes[x] == boxes[i]){
            ret = max(ret, solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1,          dp));
         }
      }
      return dp[i][j][k] = ret;
   }
   int removeBoxes(vector<int>& boxes) {
      int n = boxes.size();
      vector < vector < vector <int > > > dp(n + 1, vector < vector <int> > (n + 1, vector <int>(n + 1, -1)));
      return solve(boxes, 0, n - 1, 0, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,2,2,2,4,4,3,1};
   cout << (ob.removeBoxes(v));
}

इनपुट

{1,3,2,2,2,4,4,3,1}