C++で回文部分文字列を繰り返し削除して文字列を消去する最小ステップ数を求める方法

問題文

数字のみで構成された文字列が与えられます。1ステップごとに「回文になっている部分文字列」を1つ削除できるとき、この文字列をすべて削除するために必要な最小ステップ数を求めます。部分文字列を削除した後は、残りの部分同士が連結されます。

例

入力文字列が「3441213」の場合、最小2ステップで削除できます。

• まず「121」を削除します。残りの文字列は「3443」になります
• 残った「3443」は回文なので、まとめて削除します

アルゴリズム(考え方)

この問題は動的計画法(DP)を使うことで効率的に解けます。

1. dp[i][j] を「部分文字列 s[i, j] を削除するのに必要なステップ数」と定義します
2. 各文字は単独で削除されるか、何らかの回文部分文字列の一部として削除されます。前者の場合は、その文字だけを削除して部分問題 (i+1, j) に帰着させます
3. 後者の場合は、現在の文字と同じ文字が右側に出現する位置をすべて列挙します。そのインデックスを K とすると、問題は2つの部分問題 (i+1, K−1) と (K+1, j) に分解できます
4. (i+1, K−1) という部分問題に到達できるのは、両端の同じ文字を先に削除すれば中間の部分文字列だけが残るからです
5. さらに、先頭の2文字が同じ場合には、直接部分問題 (i+2, j) に帰着できるケースも考慮する必要があります

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
   int n = str.length();
   int dp[n + 1][n + 1];
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
         dp[i][j] = 0;
      }
   }
   for (int len = 1; len <= n; len++) {
      for (int i = 0, j = len - 1; j < n; i++, j++) {
         if (len == 1)
            dp[i][j] = 1;
         else {
            dp[i][j] = 1 + dp[i + 1][j];
            if (str[i] == str[i + 1]) {
               dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
            }
            for (int K = i + 2; K <= j; K++){
               if (str[i] == str[K]) {
                  dp[i][j] =
                  min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
               }
            }
         }
      }
   }
   return dp[0][n - 1];
}
int main() {
   string str = "3441213";
   cout << "Minimum required steps: " <<
   getMinRequiredSteps(str) << endl;
   return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

実行結果

Minimum required steps: 2

計算量について

この解法は区間DPに基づいているため、長さ n の文字列に対して時間計算量は O(n³)、空間計算量は O(n²) となります。短〜中程度の長さの文字列であれば十分に高速に動作します。