C++で回文部分配列を削除する：区間DPによる最小操作回数の求め方

問題概要

整数配列 arr が与えられます。1回の操作では、インデックス i から j（i <= j）までの範囲にある「回文」となる部分配列を選んで削除することができます。ここで注意したいのは、部分配列を削除した後、その左右にあった残りの要素が移動して、削除によって生じた隙間を自動的に埋めるという点です。このとき、配列からすべての数値を取り除くために必要な最小の操作回数を求めるのが本問題の目的です。

例として、入力が arr = [1,3,4,1,5] の場合を考えてみましょう。このときの出力は 3 になります。具体的には、「[4] を削除」→「[1,3,1] を削除」→「[5] を削除」という順序で操作することで、合計3回ですべての要素を除去できるためです。

解法の考え方（区間DP）

この問題は動的計画法（DP）、特に区間ごとの状態を管理する「区間DP」の手法で効率よく解けます。dp[i][j] を「インデックス i から j までの部分配列をすべて削除するのに必要な最小操作回数」と定義し、短い区間から順に答えを埋めていきます。

アルゴリズムの手順

• n を arr のサイズとします。
• (n + 1) × (n + 1) のサイズを持つ2次元配列 dp を用意します。
• 区間の長さ l を 1 から n まで1ずつ増やしながら、以下を繰り返します。
  • i = 0、j = l − 1 から開始し、j < n の間、i と j を1ずつ増やしながら処理します。
    • l == 1 の場合（長さ1の区間）：dp[i][j] = 1 とします。長さ1の部分配列は常に回文であるため、1回の操作で削除できます。
    • それ以外の場合：
      • まず、先頭の arr[i] を単独で削除するケースとして dp[i][j] = 1 + dp[i + 1][j] と初期化します。
      • i + 1 < n かつ arr[i] == arr[i + 1] の場合は、隣接する同じ2要素が回文になるためまとめて削除でき、dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]) で更新します。
      • さらに、k を i + 2 から j まで動かしながら、arr[i] == arr[k] となる位置を探します。見つかった場合は dp[i][j] = min(dp[i][j], dp[i + 1][k − 1] + dp[k + 1][j]) で更新します。これは「内側の区間 [i + 1, k − 1] を先に削除すれば arr[i] と arr[k] が隣接して回文となり、外側の残り区間も独立に処理できる」という発想に基づいています。
• 最終的に dp[0][n − 1] を返します。これが配列全体を削除するための最小操作回数となります。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int> > dp(n + 1, vector<int>(n + 1));
        for (int l = 1; l <= n; l++) {
            for (int i = 0, j = l - 1; j < n; i++, j++) {
                if (l == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 1 + dp[i + 1][j];
                    if (i + 1 < n && arr[i] == arr[i + 1])
                    dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
                    for (int k = i + 2; k <= j; k++) {
                        if (arr[i] == arr[k]) {
                            dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2};
    cout << (ob.minimumMoves(v));
}

入力

[1,2]

出力

2

この入力例では、配列 [1,2] に回文となる長さ2以上の部分はなく、各要素を1回ずつ削除するしかないため、出力は 2 になります。

計算量について

このアルゴリズムの時間計算量は O(n³)、空間計算量は O(n²) です。すべての区間 (i, j) の組み合わせに対して、分割位置 k を最大 O(n) 回試すためです。n が数百程度までの入力であれば十分に高速に動作します。