在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），-

• 如果l与1相同，则-

• 除此以外

• dp [i，j]：= 1

• 如果arr [i]与arr [k]相同，则-

• dp [i，j]：= dp [i，j]和dp [i + 1，k-1] + dp [k + 1，j]的最小值

• dp [i，j]：= dp [i，j]和1 + dp [i + 2，j]的最小值

• dp [i，j]：= 1 + dp [i + 1，j]

• 如果i + 1 <n并且arr [i]与arr [i + 1]相同，则-

• 对于初始化k：= i + 2，当k <= j时，更新（将k增加1），-

• 对于初始化i：= 0，j：= l-1，当j <n时，更新（i增加1），（j增加1），-

• 返回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