C++で解く回文分割 III（Palindrome Partitioning III）― DPとメモ化再帰による最小文字変更数の求め方

問題の概要

小文字の英字のみからなる文字列 s と整数 k が与えられます。このとき、次の条件を満たす必要があります。

• まず、必要に応じて s 内の一部の文字を、別の小文字の英字に変更します。
• その後、文字列 s を k 個の部分文字列に分割し、それぞれが回文になるようにします。

求めるのは、この分割を実現するために変更が必要な文字数の最小値です。

具体例

例えば、文字列が "ababbc"、k = 2 の場合、答えは 1 になります。わずか 1 文字の変更で 2 つの回文に分割できるためです。末尾の c を b に変更すれば "bbb" と "aba" に、後ろから 2 番目の b を c に変更すれば "cbc" と "aba" にそれぞれ分割できます。

解法のアプローチ

この問題は、動的計画法（DP）とメモ化再帰を組み合わせることで効率的に解けます。全体の流れは次の通りです。

ステップ 1：区間ごとの変更コストを前計算する

サイズ n × n の二次元配列 dp を用意し、dp[i][j] に「部分文字列 s[i..j] を回文にするために必要な最小の文字変更数」を格納します。計算は部分文字列の長さ l を 2 から n まで伸ばしながら行います。

• l == 2 の場合：dp[i][j] = (s[i] != s[j]) ? 1 : 0
• それ以外の場合：dp[i][j] = dp[i+1][j-1] + (s[i] != s[j])

つまり、両端の文字が一致していれば内側の結果をそのまま使い、一致していなければコストを 1 加算します。

ステップ 2：メモ化再帰で最小分割コストを求める

関数 solve(s, idx, k, dp) を次のように定義します。

1. idx が文字列の長さと等しい場合：k が 0 なら 0 を返し、そうでなければ 1000（実質的な不正値）を返します。
2. memo[idx][k] が -1 以外なら、計算済みなのでその値を返します（メモ化）。
3. k <= 0 の場合は INT_MAX を返します。
4. ans を無限大で初期化し、分割位置 i を idx から文字列末尾まで動かしながら、dp[idx][i] + solve(s, i + 1, k - 1, dp) の最小値を求めます。
5. 結果を memo[idx][k] に保存して返します。

メイン側では、文字列長 n を取得し、memo を -1 で初期化した上で、solve(s, 0, k, dp) を呼び出して答えを得ます。

C++での実装例

#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

計算量について

区間コストの前計算には O(n²)、メモ化再帰の状態数は O(n × k)、各状態からの遷移が O(n) であるため、全体の時間計算量は O(n² × k)、空間計算量は O(n²) となります。競技プログラミングやコーディング面接においても十分に高速な手法です。