Burst Balloons：逆向き区間DP

値 nums を持つ n 個のバルーンが与えられたとき、バルーン i を破裂させると、nums[i-1] * nums[i] * nums[i+1] 枚のコインを獲得します（自身と、その時点での隣接バルーンの積です）。破裂すると隣接バルーン同士が隣り合います。すべてのバルーンを破裂させて獲得できるコインの最大値を求めてください。単純なシミュレーションでは、破裂するたびに隣接関係が変わるため困難です。逆向きの区間DPを使うと、この難しさを巧みに回避できます。

dp[i][j] を区間 [i, j] のバルーンを破裂させて得られるコインの最大値と定義し、どのバルーンを最初に破裂させるかを考えると、問題が生じます。バルーン k を最初に破裂させるには、nums[k-1] と nums[k+1] がその時点での隣接バルーンでなければなりません。しかし、これらのバルーンは後で破裂する可能性があり、隣接関係が動的に変化します。そのため、前向きの方向では状態をきれいに定義するのが困難です。

ポイントは、区間 [i, j] でどのバルーンが最後に破裂するかを考えることです。バルーン k が [i, j] で最後に破裂するとき、区間 [i, j] 内の他のバルーンはすべてすでに消えています。したがって、バルーン k の隣接バルーンは、区間のすぐ外側にある境界バルーン nums[i-1] と nums[j+1] に正確に定まります。これにより、最後の破裂で得られるコイン数を決定的に計算できます。これは、それ以前の破裂順序に依存しません。

センチネルバルーンを追加します。nums の先頭と末尾に 1 を追加して、nums = [1] + nums + [1] とします。dp[i][j] は、インデックス i と j の間（両端を除く）にあるすべてのバルーンを破裂させて得られるコインの最大値と定義します。このとき、nums[i] と nums[j] は残っている境界バルーンです。漸化式は、区間 (i, j) 内の最後のバルーンの候補 k すべてについて、dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) となります。

配列にセンチネルを追加し、DPテーブルを0（空の区間はコイン0）で初期化して、区間の長さが短いものから順に埋めます。最終的な答えは dp[0][n+1] です。これは、センチネルを固定された境界として、元のすべてのバルーンを破裂させて得られるコインの最大値を表します。

[3, 1, 5, 8] を [1, 3, 1, 5, 8, 1] に拡張します（インデックスは 0～5）。求めるのは dp[0][5] です。長さ=2の区間（内部にバルーンが1つある場合）では、dp[0][2] = 1*3*1=3、dp[1][3]=3*1*5=15、dp[2][4]=1*5*8=40、dp[3][5]=5*8*1=40 となります。計算を進めると、{3,1,5,8} の中では、先に両隣を破裂させてから 1 を最後に破裂させるのが最適で、合計167コインになります。

O(n²) 個の区間があり、各区間でO(n) 個の分割位置を試すため、時間計算量は O(n³) です。空間計算量は、DPテーブルにO(n²) 必要です。n = 500 個のバルーンの場合、これは1億2500万回の操作になりますが、面接で想定される制約であれば実行可能です。センチネルで配列を拡張すると境界処理が簡単になります。これがなければ、i-1 と j+1 が範囲内かどうかを明示的に確認する必要があります。

同じ解法を @lru_cache を使ったトップダウン形式で書くこともできます。面接中に導出する場合は、こちらのほうが直感的かもしれません。solve(i, j) を開区間 (i, j) 内の最大コイン数と定義します。この関数は最後に破裂させる k の候補をすべて試し、結果をメモ化します。どちらの方法も、時間計算量と空間計算量は同じです。

よくあるミスは、dp[i][j] を区間 [i,j] の最初のバルーンを破裂させたときのコイン数として定義してしまうことです。最初の破裂で得られるコイン数は、まだ破裂していない隣接バルーンに依存しますが、その隣接バルーンの状態はアルゴリズムの進行に伴って変化するため、これはうまくいきません。境界が残っている要素に依存する区間DPでは、常に最後の要素について考えてください。

値1のセンチネルを使うのは、乗算における単位元として機能するためです。境界バルーンを最後に破裂させる場合、そのコイン数は boundary * last * boundary = 1 * last * 1 = last となります。0を使うとコイン数が0になってしまい不適切で、別の値を使うと計算結果が変わってしまいます。センチネルを使うことで、左端と右端のバルーンを特別扱いせず、すべての境界ケースをきれいに統一できます。

標準的な区間DP（行列連鎖）では、分割位置 k は問題を2つの部分問題に分け、それぞれを独立に解く位置を表します。一方、バルーン破裂では、k は区間内で最後に破裂するバルーンです。k が境界として残っているという条件のもとで、2つの部分区間 [i,k] と [k,j] を独立に扱えます。この逆向きの視点こそが、バルーン破裂問題を区間DPで解けるようにする創造的な着眼点です。

このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

このレッスンでは、風船を割ると隣接する風船が予測不能に変化するため、前向きのシミュレーションはうまくいかないこと、逆向きの着眼点として、区間内で最後に割る風船を k と定めると、隣接する風船が nums[i] と nums[j] になること、そしてセンチネルによるパディングを用いた漸化式 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) によって、O(n³) の解法が得られることを学びました。次はナップサックDPに移り、古典的な0/1ナップサックとその空間最適化から始めます。