C++ में पैलिंड्रोम रिमूवल

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

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

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

• n := arr का आकार

• आकार (n + 1) x (n + 1) का एक 2D ऐरे dp परिभाषित करें

• l := 1 से शुरू करें, जब l <= n, अपडेट करें (l को 1 से बढ़ाएं), करें:

  • i := 0, j := l - 1 से शुरू करें, जब j < n, अपडेट करें (i को 1 से बढ़ाएं), (j को 1 से बढ़ाएं), करें:

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

      • dp[i, j] := 1

    • अन्यथा:

      • dp[i, j] := 1 + dp[i + 1, j]

      • यदि i + 1 < n और arr[i], arr[i + 1] के समान है, तो:

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

      • k := i + 2 से शुरू करें, जब k <= j, अपडेट करें (k को 1 से बढ़ाएं), करें:

        • यदि arr[i], arr[k] के समान है, तो:

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

  • dp[0, n - 1] लौटाएं

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

  उदाहरण

  #include <bits/stdc++.h>
  using namespace std;
  
  class Solution {
  public:
      int minimumMoves(vector& arr) {
          int n = arr.size();
          vector> dp(n + 1, vector(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];
      }
  };
  
  int main() {
      Solution ob;
      vector v = {1,2};
      cout << (ob.minimumMoves(v));
  }

  इनपुट

  [1,2]

  आउटपुट

  2