C++でのパリンドロームパーティショニングIII

小文字と整数kを含む文字列sがあるとします。いくつかのプロパティを維持する必要があります。これらは-

• まず、sの一部の文字（必要な場合）を他の小文字の英字に変更する必要があります。
• 次に、文字列sをk個の部分文字列に分割して、各部分文字列が回文になるようにします。

文字列を分割するために変更する必要のある最小文字数を見つける必要があります。

したがって、文字列が「ababbc」のようで、k =2の場合、1文字を変更してこれを2つの回文文字列に分割する必要があるため、答えは1になります。したがって、cをbに変更するか、最後から2番目のbをcに変更すると、「bbb」または「cbc」のような1つの回文を取得でき、別の回文は「aba」になります。

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

• サイズが105x105の配列メモを定義します。
• 関数solve（）を定義します。これには、s、idx、k、1つの2D配列> dp、
が必要です。
• idxがsのサイズと同じ場合、-
  • kが0の場合は戻り、それ以外の場合は0を返します
• memo [idx] [k]が-1に等しくない場合、-
  • return memo [idx] [k]
• k <=0の場合、-
  • return inf
• ans：=inf
• iを初期化する場合：=idx、i
• ans：=最小のansとdp [idx] [i] +関数solve（s、i + 1、k-1、dp）を呼び出す

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

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int memo[105][105];
   lli solve(string s, int idx, int k, vector < vector <int> > &dp){
      if(idx == s.size()) {
         return k == 0? 0 : 1000;
      }
      if(memo[idx][k] != -1) return memo[idx][k];
      if(k <= 0)return INT_MAX;
      lli ans = INT_MAX;
      for(int i = idx; i < s.size(); i++){
         ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
      }
      return memo[idx][k] = ans;
   }
   int palindromePartition(string s, int k) {
      int n = s.size();
      memset(memo, -1, sizeof(memo));
      vector < vector <int> > dp(n, vector <int>(n));
      for(int l =2; l <= n; l++){
         for(int i = 0, j = l - 1; j <n; j++, i++){
            if(l==2){
               dp[i][j] = !(s[i] == s[j]);
            }else{
               dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
            }
         }
      }
      return solve(s, 0, k, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.palindromePartition("ababbc", 2));
}

入力

“ababbc”

出力

1