C++ पर पालिंड्रोम हटाना

मान लीजिए कि हमारे पास एआर नामक एक पूर्णांक सरणी है, अब एक चाल में हम इंडेक्स i से j तक एक पैलिंड्रोमिक सबरे का चयन कर सकते हैं जहां i <=j, और दिए गए सरणी से उस सबरे को हटा दें। हमें यह ध्यान रखना होगा कि एक सबअरे को हटाने के बाद, बाईं ओर और उस सबएरे के दायीं ओर के तत्व हटाने के द्वारा छोड़े गए गैप को भरने के लिए चले जाते हैं। हमें सरणी से सभी नंबरों को हटाने के लिए आवश्यक न्यूनतम चालों की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट arr =[1,3,4,1,5] जैसा है, तो आउटपुट 3 होगा, जैसा कि हम इस क्रम में हटा सकते हैं, [4] को हटा सकते हैं और फिर [1,3,1] को हटा सकते हैं। [5] हटाएं।

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

• n :=गिरफ्तारी का आकार

• एक 2D सरणी dp आकार (n + 1) x (n + 1)

  . को परिभाषित करें

• इनिशियलाइज़ l के लिए :=1, जब l <=n, अपडेट करें (l को 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ करने के लिए i :=0, j :=l-1, जब j

    • यदि l 1 के समान है, तो -

      • डीपी [आई, जे]:=1

    • अन्यथा

      • डीपी [आई, जे]:=1 + डीपी [i + 1, जे]

      • अगर i + 1

        • dp[i, j] :=न्यूनतम dp[i, j] और 1 + dp[i + 2, j]

      • k :=i + 2 को इनिशियलाइज़ करने के लिए, जब k <=j, अपडेट करें (k को 1 से बढ़ाएँ), करें -

        • अगर गिरफ्तारी [i] गिरफ्तारी [के] के समान है, तो -

          • dp[i, j] :=न्यूनतम dp[i, j] और dp[i + 1, k - 1] + dp[k + 1, j]

• वापसी डीपी [0, एन -1]

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minimumMoves(vector<int>& arr) {
      int n = arr.size();
      vector<vector<int> > dp(n + 1, vector<int>(n + 1));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            if (l == 1) {
               dp[i][j] = 1;
            } else {
               dp[i][j] = 1 + dp[i + 1][j];
               if (i + 1 < n && arr[i] == arr[i + 1])
               dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
               for (int k = i + 2; k <= j; k++) {
                  if (arr[i] == arr[k]) {
                     dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                  }
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minimumMoves(v));
}

इनपुट

[1,2]

आउटपुट

2