C ++中的回文分割III

假设我们有一个包含小写字母和整数k的字符串s。我们必须维护一些属性。这些是-

• 首先，我们必须将s的某些字符（如果需要）更改为其他小写英文字母。

• 然后将字符串s分为k个子字符串，以使每个子字符串都是回文。

我们必须找到为分割字符串而需要更改的最少字符数。

因此，如果字符串像“ ababbc”并且k = 2，则答案将是1，因为我们必须更改一个字符以将其分成两个回文字符串。因此，如果将c更改为b，或将倒数第二个b更改为c，则可以得到一个回文，如“ bbb”或“ cbc”，而另一个回文为“ aba”。

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为105 x 105的数组备忘。

• 定义一个函数solve()，它将使用s，idx，k，一个2D数组> dp，

• 如果idx与s的大小相同，则-

• 当k为0时返回，否则为0，否则返回1000

• 如果memo [idx] [k]不等于-1，则-

• 返回备忘录[idx] [k]

• 如果k <= 0，则-

• 返回信息

• ans：= inf

• 对于初始化i：= idx，当i <s的大小时，更新（将i增加1），执行-

• ans：= ans和dp [idx] [i]的最小值+调用函数solve（s，i + 1，k-1，dp）

• 返回memo [idx] [k] = ans

• 在主要方法中，执行以下操作

• n：= s的大小

• 用-1填充备忘录

• 定义一个大小为nxn的2D数组dp

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

• 如果l与2相同，则-

• dp [i] [j]：=当s [i]与s [j]不同时为true

• 除此以外

• dp [i] [j]：= dp [i + 1] [j-1] + 0，如果s [i]与s [j]相同

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

• 返回solve(s,0,k,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