C++でパリンドロームサブリストを削除するために必要な操作の数を見つけるためのプログラム

numsという番号のリストがあるとします。ここで、回文であるサブリストを削除する操作について考えてみましょう。リストが空になるように、必要な操作の最小数を見つける必要があります。

したがって、入力がnums =[6、2、4、4、2、10、6]のような場合、最初にサブリスト[2、4、4、2]を削除してから、リストは[6、10、6]のようなものです。これも回文素数なので、リストを空にするには削除します。

これを解決するには、次の手順に従います-

• サイズが105x105の配列dpを定義します。

• 関数dfs（）を定義します。これには、i、j、配列v、

  が必要です。

• ret：=inf

• i> jの場合、-

  • 0を返す

• iがjと同じ場合、-

  • 1を返す

• j-iが1と同じ場合、-

  • return（v[i]がv[j]と同じ場合は1、それ以外の場合は2）

• i + 1 <=jであり、v[i]がv[i + 1]と同じである場合、-

  • ret：=1 + dfs（i + 2、j、v）

• dp [i、j]が-1に等しくない場合、-

  • dp [i、j]

    を返します

• ret：=最小（ret、1 +（最小（dfs（i + 1、j、v）およびdfs（i、j-1、v）））

• v[i]がv[j]と同じ場合、-

  • ret：=retとdfs（i + 1、j-1、v）の最小値

• 初期化k：=i + 2の場合、k

  • v[i]がv[k]と同じ場合、＆minnus;

    • ret：=retとdfsの最小値（（i + 1、k-1、v）+ dfs（k + 1、j、v））

• dp [i、j] =ret

  を返します

• メインの方法から、次のようにします-

• dpを-1で埋める

• n：=numsのサイズ

• dfs（0、n-1、nums）を返す

例

理解を深めるために、次の実装を見てみましょう-

#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