C++で解く「バルーンを割る」問題（Burst Balloons）――動的計画法による最適解

問題概要

n個の風船があり、それぞれに0からn-1までのインデックスが振られています。各風船には配列 nums で表される数字が書かれており、すべての風船を割ることが目標です。風船 i を割ると、nums[i-1] × nums[i] × nums[i+1] の積に相当する枚数のコインを獲得できます。風船を割った後は、その左右にあった風船 i-1 と i+1 が隣接します。賢い順序で風船を割り、獲得できるコインの合計を最大化しましょう。

例えば、入力が [3, 1, 5, 7] の場合、答えは 148 になります。まず配列は [3, 1, 5, 7] の状態から始まります。最初に 1 を割ると 3 × 1 × 5 = 15 枚のコインが得られ、配列は [3, 5, 7] になります。次に 5 を割ると 3 × 5 × 7 = 105 枚が得られ、配列は [3, 7] になります。続いて 3 を割ると 1 × 3 × 7 = 21 枚が得られ、配列は [7] となります。最後に残った 7 を割ると 7 枚が加わります。合計は 15 + 105 + 21 + 7 = 148 です。

アルゴリズム：区間DPによるアプローチ

この問題は動的計画法（DP）で効率的に解けます。ポイントは、「風船 i を最後に割る」という視点で考えることです。区間 [l, r] 内のすべての風船を割ったときに得られる最大コイン数を dp[l][r] として定義すると、以下の手順で計算できます。

• n を配列 a のサイズとします。
• n が 0 の場合は 0 を返します。
• n × n の2次元配列 dp を定義します。
• l を n-1 から 0 まで減らしながら繰り返します。
  • r を l から n-1 まで増やしながら繰り返します。
    • i を l から r まで増やしながら繰り返します。
      • y := （i + 1 < n なら）dp[i+1][r]、範囲外なら 0
      • z := （l - 1 >= 0 なら）a[l-1]、範囲外なら 1（番兵として扱う）
      • w := （r + 1 < n なら）a[r+1]、範囲外なら 1
      • x := （i - 1 >= 0 なら）dp[l][i-1]、範囲外なら 0 ＋ y ＋ z × w × a[i]
      • dp[l][r] := dp[l][r] と x の大きい方の値
• dp[0][n-1] を返します。

境界の外側を 1 として扱うことで、端の風船を割る場合も同じ式で統一的に処理できるのがこの手法の美しい点です。計算量は O(n³)、空間計算量は O(n²) となります。

実装例

以下に C++ での実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxCoins(vector<int>& a) {
      int n = a.size();
      if(!n)return 0;
      vector < vector <int>> dp(n,vector <int> (n));
      for(int l = n-1;l>=0;l--){
         for(int r=l;r<n;r++){
            for(int i =l;i<=r;i++){
               dp[l][r] = max(dp[l][r],(i-1>=0?dp[l][i-1]:0) +(i+1<n?dp[i+1][r]:0)+((l-1>=0?a[l-1]:1 )*(r+1<n?a[r+1]:1)*a[i]));
            }
         }
      }
      return dp[0][n-1];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,5,7};
   cout << (ob.maxCoins(v));
}

入力

[3,1,5,7]

出力

148

まとめ

バルーン割り問題は一見単純な貪欲法では解けないため、「どの風船を最後に割るか」を区間ごとに考える区間DPが有効です。境界条件を 1 として統一することで実装がシンプルになり、O(n³) の時間計算量で最適解を求められます。類似の区間DP問題（行列チェーン乗算など）にも応用できる重要なパターンなので、ぜひマスターしておきましょう。