C++での回文の削除

arrという整数配列があるとします。これで、1回の移動で、インデックス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を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