C++で回文サブリストを削除してリストを空にする最小操作回数を求めるプログラム

数値のリスト nums が与えられます。ここで、「リスト内の連続した部分リスト(サブリスト)のうち、回文になっているものを削除する」という操作を考えます。この操作を繰り返してリストを空にするとき、必要となる最小の操作回数を求めるのが本問題です。

例えば、入力が nums = [6, 2, 4, 4, 2, 10, 6] の場合、答えは 2 になります。まず部分リスト [2, 4, 4, 2](回文)を削除すると、残りのリストは [6, 10, 6] となり、これも回文なので削除できます。合計 2 回の操作でリストを空にできるためです。

解法のアプローチ

この問題は、区間を対象としたメモ化再帰(区間 DP)を用いることで効率的に解けます。「区間 [i, j] を空にするのに必要な最小操作回数」を再帰的に求め、その結果を dp テーブルにキャッシュすることで、同じ区間の再計算を防ぎます。

アルゴリズムの手順

• サイズ 105 × 105 の 2 次元配列 dp を定義します(未計算の状態は -1 で表します)。
• 関数 dfs(i, j, v) を定義します。これは「区間 [i, j] を空にするための最小操作回数」を返します。
• ret を無限大で初期化します。
• i > j の場合(空区間)、0 を返します。
• i == j の場合(要素が 1 個)、1 回の操作で削除できるので 1 を返します。
• j - i == 1 の場合(要素が 2 個)、v[i] == v[j] なら 1、そうでなければ 2 を返します。
• i + 1 <= j かつ v[i] == v[i + 1] の場合、隣接する同じ要素をまとめて削除できるので、ret := 1 + dfs(i + 2, j, v) で候補を更新します。
• dp[i][j] != -1 の場合、すでに計算済みなのでその値を返します。
• ret を 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v)) と比較して小さい方に更新します(先頭または末尾の 1 要素を単独で削除するケース)。
• v[i] == v[j] の場合、両端を同時に削除できるので、ret と dfs(i + 1, j - 1, v) の小さい方を採用します。
• k = i + 2 から k < j までループし、v[i] == v[k] のときは、v[i] と v[k] を端点とする回文を削除するケースとして、ret と dfs(i + 1, k - 1, v) + dfs(k + 1, j, v) の小さい方を採用します。
• 最後に dp[i][j] = ret を返します。

メイン関数での処理

• dp 配列全体を -1 で初期化します。
• n を nums のサイズとします。
• dfs(0, n - 1, nums) の結果を返します。

C++ 実装例

以下の実装を見ると、理解がより深まります。

#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
    int ret= INT_MAX;
    if(i > j)
       return 0;
    if(i == j)
       return 1;
    if(j - i == 1){
       return v[i] == v[j] ? 1 : 2;
    }
    if(i + 1 <= j && v[i] == v[i + 1]){
       ret = 1 + dfs(i + 2, j, v);
    }
    if(dp[i][j] != -1) return dp[i][j];
       ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
    if(v[i] == v[j]){
       ret = min(ret, dfs(i + 1, j - 1, v));
    }
    for(int k = i + 2; k < j; k++){
       if(v[i] == v[k]){
          ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
       }
    }
    return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
    memset(dp , -1, sizeof dp);
    int n = nums.size();
    return dfs(0, n - 1, nums);
}
int main(){
    vector<int> v = {6, 2, 4, 4, 2, 10, 6};
    cout << solve(v);
}

入力

{6, 2, 4, 4, 2, 10, 6}

出力

2

計算量の目安

状態数は O(n²)、各状態からの遷移に最大 O(n) かかるため、時間計算量は O(n³)、dp テーブルのための空間計算量は O(n²) となります。メモ化により、同じ区間に対する探索が一度しか行われない点が高速化のポイントです。