C++ में रिमूव बॉक्सेस समस्या

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

आपको प्राप्त होने वाले अधिकतम पॉइंट्स ढूंढने हैं।

समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग + मेमोइजेशन)

solve() फंक्शन परिभाषित करें जो लेता है: boxes ऐरे, i, j, k, और एक 3D ऐरे dp।
यदि i > j, तो 0 लौटाएं।
यदि dp[i][j][k] != -1, तो dp[i][j][k] लौटाएं।
ret := -INF।
जब i+1 <= j और boxes[i+1] == boxes[i], i बढ़ाएं और k बढ़ाएं।
ret := max(ret, (k+1)*(k+1) + solve(boxes, i+1, j, 0, dp))।
x = i+1 से j तक लूप करें:
- यदि boxes[x] == boxes[i]:
  - ret := max(ret, solve(boxes, i+1, x-1, 0, dp) + solve(boxes, x, j, k+1, dp))
dp[i][j][k] = ret लौटाएं।
मुख्य मेथड से:
- n := boxes.size()
- आकार (n+1) x (n+1) x (n+1) का 3D ऐरे dp परिभाषित करें, -1 से भरें।
- solve(boxes, 0, n-1, 0, dp) लौटाएं।

C++ कार्यान्वयन

#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++);
        
        // विकल्प 1: वर्तमान ग्रुप को अभी हटाएं
        ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
        
        // विकल्प 2: बाद में हटाने के लिए समान रंग के बॉक्स ढूंढें
        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);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 3, 2, 2, 2, 4, 4, 3, 1};
    cout << ob.removeBoxes(v);
    return 0;
}

इनपुट

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