C++でボックス削除問題を攻略！区間DPで最大得点を求める方法

問題概要

ここに、色の異なる複数の箱が一列に並んでいるとします。それぞれの色は異なる正の整数で表されます。プレイヤーは複数のラウンドに分けて箱を取り除き、すべての箱をなくすことを目指します。各ラウンドでは同じ色が連続した箱（k個、k >= 1）を選んでまとめて取り除くことができ、その際に k × k 点の得点を獲得できます。

例えば、入力が [1,3,2,2,2,4,4,3,1] の場合、出力は 21 になります。この記事では、獲得できる得点を最大化するためのアルゴリズムを解説します。

出力が 21 になる理由

実際の消し方の一例を見てみましょう。

1. [1,3,2,2,2,4,4,3,1] → 3個の「2」を消去して 3×3 = 9点
2. [1,3,4,4,3,1] → 2個の「4」を消去して 2×2 = 4点
3. [1,3,3,1] → 2個の「3」を消去して 2×2 = 4点
4. [1,1] → 2個の「1」を消去して 2×2 = 4点

合計は 9 + 4 + 4 + 4 = 21点となります。

解法のアプローチ

この問題は、単純に左から順番に消していくだけでは最大得点を達成できないことがあります。離れた位置にある同色の箱を、間の箱を先に消してからつなげて大きな塊にする方が有利だからです。そこで、メモ化再帰を用いた区間DPで解きます。以下の手順に従います。

• solve() 関数を定義します。引数は配列 boxes、インデックス i・j・k、そして3次元配列 dp です。
• i > j の場合 → 0 を返します。
• dp[i][j][k] が -1 以外の場合 → 計算済みなので、その値を返します。
• ret := -∞ で初期化します。
• i + 1 <= j かつ boxes[i + 1] と boxes[i] が同じ色である限り、i を 1 増やしながら k も 1 増やします（連続する同色の箱をひとまとまりとして処理します）。
• ret := max(ret, (k + 1) × (k + 1) + solve(boxes, i + 1, j, 0, dp))
• x := i + 1 から x <= j までループします。
  • boxes[x] と boxes[i] が同じ色の場合 →
    • ret := max(ret, solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp))
• dp[i][j][k] = ret を返します。

パラメータ k は、「現在注目している箱と同じ色で、区間の外側に存在し、あとで一緒に消せる箱の数」を追跡する役割を担います。これにより、間にある別の色の箱を先に除去してから同色の箱をつなげる戦略も正しく評価できます。

続いて、main 関数では次の処理を行います。

• n := boxes のサイズを取得します。
• (n + 1) × (n + 1) × (n + 1) の3次元配列 dp を定義し、全要素を -1 で初期化します。
• solve(boxes, 0, n - 1, 0, dp) の結果を返します。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int solve(vector <int>& boxes, int i, int j, int k, vector < vector < vector <int > > >& dp){
      if(i > j) return 0;
      if(dp[i][j][k] != -1) return dp[i][j][k];
      int ret = INT_MIN;
      for(; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
      ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
      for(int x = i + 1; x <= j; x++){
         if(boxes[x] == boxes[i]){
            ret = max(ret, solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1,          dp));
         }
      }
      return dp[i][j][k] = ret;
   }
   int removeBoxes(vector<int>& boxes) {
      int n = boxes.size();
      vector < vector < vector <int > > > dp(n + 1, vector < vector <int> > (n + 1, vector <int>(n + 1, -1)));
      return solve(boxes, 0, n - 1, 0, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,2,2,2,4,4,3,1};
   cout << (ob.removeBoxes(v));
}

入力例

{1,3,2,2,2,4,4,3,1}

出力例

21

計算量について

DPの状態数は O(n³)、各状態からの遷移に最大 O(n) を要するため、全体の時間計算量は O(n⁴)、空間計算量は O(n³) となります。メモ化により同じ状態の再計算を避けることで、指数的な爆発を防いでいるのがポイントです。