C++ এ প্যালিনড্রোম অপসারণ

ধরুন আমাদের একটি পূর্ণসংখ্যার অ্যারে আছে যাকে বলা হয় arr, এখন আমরা একটি প্যালিন্ড্রোমিক সাবয়ারে নির্বাচন করতে পারি সূচক i থেকে j পর্যন্ত যেখানে i <=j, এবং প্রদত্ত অ্যারে থেকে সেই সাবয়ারেটি সরিয়ে ফেলতে পারি। আমাদের মনে রাখতে হবে যে একটি সাবঅ্যারে অপসারণের পরে, সেই সাবঅ্যারেটির বাম এবং ডানদিকের উপাদানগুলি অপসারণের মাধ্যমে অবশিষ্ট শূন্যস্থান পূরণ করতে চলে যায়। অ্যারে থেকে সমস্ত সংখ্যা সরানোর জন্য আমাদের ন্যূনতম সংখ্যক চাল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি arr =[1,3,4,1,5] এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমরা এই ক্রমানুসারে রিমুভ করতে পারি, রিমুভ [4] তারপর রিমুভ [1,3,1] তারপর সরান [৫]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=arr এর আকার

• আকারের একটি 2D অ্যারে dp সংজ্ঞায়িত করুন (n + 1) x (n + 1)

• আরম্ভ করার জন্য l :=1, যখন l <=n, আপডেট করুন (l 1 দ্বারা বৃদ্ধি করুন), করুন −

  • আরম্ভ করার জন্য i :=0, j :=l - 1, যখন j

    • যদি l 1 এর সমান হয়, তাহলে −

      • dp[i, j] :=1

    • অন্যথায়

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

      • যদি 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<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