সি++-এ প্যালিনড্রোম রিমুভাল

ধরা যাক 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 ১ করে বাড়ান), করুন -

  • i := 0, j := l - 1 থেকে শুরু করুন, যখন j < n, (i ১ করে বাড়ান), (j ১ করে বাড়ান), করুন -

    • যদি l ১-এর সমান হয়, তবে -

      • 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 ১ করে বাড়ান), করুন -

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