查找在C ++中删除回文子列表所需的操作数的程序

假设我们有一个称为nums的数字列表。现在，让我们考虑一个操作，其中删除一些回文表子列表。我们必须找到所需的最少操作数，以使列表为空。

因此，如果输入类似于nums = [6，2，4，4，4，2，10，6]，则输出将为2，因为我们可以先删除子列表[2，4，4，2]，然后删除list类似于[6，10，6]这也是一个回文，所以将其删除以使列表为空。

例  

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
   int ret= INT_MAX;
   if(i > j)
      return 0;
   if(i == j)
      return 1;
   if(j - i == 1){
      return v[i] == v[j] ? 1 : 2;
   }
   if(i + 1 <= j && v[i] == v[i + 1]){
      ret = 1 + dfs(i + 2, j, v);
   }
   if(dp[i][j] != -1) return dp[i][j];
      ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
   if(v[i] == v[j]){
      ret = min(ret, dfs(i + 1, j - 1, v));
   }
   for(int k = i + 2; k < j; k++){
      if(v[i] == v[k]){
         ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
      }
   }
   return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
   memset(dp , -1, sizeof dp);
   int n = nums.size();
   return dfs(0, n - 1, nums);
}
int main(){
   vector<int> v = {6, 2, 4, 4, 2, 10, 6};
   cout << solve(v);
}

输入值

{6, 2, 4, 4, 2, 10, 6}

2