C++での回文分割II – 最小カット数を動的計画法で求める方法

問題概要

文字列 s が与えられたとき、この文字列を複数の部分文字列に分割し、すべての部分が回文になるようにするために必要な最小のカット（切り分け）回数を求めてください。

例えば、文字列が "ababba" の場合、[aba | bb | a] のように2箇所で切り分ければ各部分が回文になるため、答えは 2 回となります。

アプローチ：動的計画法

この問題は、文字列の後ろから順に「その位置以降を回文に分割するために必要な最小カット数」を配列に記録しながら計算することで、効率的に解くことができます。手順は以下の通りです。

• n := 文字列 s の文字数とする
• サイズ n + 1 の配列 res を作成する
• res[n] := -1 と初期化する（番兵として機能させる）
• i を n − 1 から 0 まで降順で繰り返す：
  • res[i] := n − i − 1（最悪値で初期化）
  • j を i から n − 1 まで繰り返す：
    • インデックス i から j までの部分文字列が回文である場合：
      • res[i] := min(res[i], 1 + res[j + 1])
• res[0] を返す

res[i] には「インデックス i 以降の部分文字列を回文に分割するのに必要な最小カット数」が格納されます。res[n] を -1 にしておくことで、文字列全体が最初から1つの回文だった場合にも、正しく 0 カットとして計算されるのがポイントです。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string A) {
    int left = 0;
    int right = A.size()-1;
    while(left < right) {
        if(A[left] != A[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}
int solve(string A) {
    int n = A.size();
    vector<int>result(n+1);
    result[n] = -1;
    for(int i=n-1;i>=0;i--) {
        result[i] = n-i-1;
        for(int j=i;j<n;j++) {
            if(isPalindrome(A.substr(i, j-i+1))) {
                result[i] = min(result[i], 1 + result[j+1]);
            }
        }
    }
    return result[0];
}
class Solution {
    public:
    int minCut(string s) {
        return solve(s);
    }
};
main(){
    Solution ob;
    cout << (ob.minCut("ababba"));
}

isPalindrome 関数は両端から中央に向かって文字を比較することで、部分文字列が回文かどうかを判定しています。solve 関数では、先ほど説明した手順に従って DP 配列 result を更新し、最終的に result[0] を返します。

入力

“ababba”

出力

2

補足：計算量について

この実装では、部分文字列ごとに毎回回文判定を行っているため、全体の計算量は O(n³) になります。事前に dp テーブルを作って「i から j までが回文かどうか」を O(1) で参照できるようにすれば、O(n²) まで高速化できます。大きな入力に対しては、その改良版の検討をおすすめします。