【徹底解説】Burst Balloons (LeetCode #312)をゼロから理解する
はじめに
みなさん、こんにちは!今回はアルゴリズム学習の定番である「Burst Balloons」(LeetCode #312)を扱います。
「風船を割る順番をどう決めるか」で最終得点が変わる、一見シンプルだけど奥が深い問題です。
この解説では、イメージしやすいように、高卒の僕が丁寧に図や例を用いながら解説します。
問題概要
問題のストーリー
-
複数の風船が一列に並んでいます。それぞれに整数が書いてあります(例:
[3, 1, 5, 8]
)。 - 好きな風船を1つ「割る」と、(左の風船の数字) × (割った風船の数字) × (右の風船の数字) が得点としてもらえます。
- もし左や右に風船が残っていなければ、その代わりに
1
として扱います。
- もし左や右に風船が残っていなければ、その代わりに
- 風船が全部割れるまでこの操作を繰り返し、合計得点を最大にするように割り順を決めてください。
例
-
nums = [3, 1, 5, 8]
の場合、ある割り方をすると以下のようになります:- 最初に
1
を割る → 左3, 右5 なので得点は3 * 1 * 5 = 15
- 次に
5
を割る → 左3, 右8 なので得点は3 * 5 * 8 = 120
- 最後に
3
と8
を割る → (もう両端しか残っていないので1 * 3 * 8 = 24
) - 合計は
15 + 120 + 24 = 159
- 最初に
しかし、実はもっと上手い割り方をすれば 167
に到達します。それをプログラムで見つける問題です。
解法
この問題は問題の性質上、貪欲法(Greedy) や順列全探索 は使用できなそうです。
それでは一体なんのアルゴリズムを使用して解くのでしょうか。
答えは
「区間DP」を使用します。
そもそもなぜ貪欲法や全探索ではダメなのか
貪欲法がダメな理由
「常にいちばん数値が大きい風船を割ればいいのでは?」と考えがちですが、
風船を割った結果「どの風船が左右に残るか」が、後の得点に大きく影響します。
途中の最適そうな選択が、最終的には損になる可能性があるため、貪欲では最適解を保証できません。
全探索がダメな理由
- 風船の数を
とすると、割る順番はn (階乗)通り存在します。`n!` -
が10以上になると、全ての順番を試すのは事実上不可能(計算量が爆発)です。n
そこで区間DPが出てくる理由
- 割る順番という要素をある区間を指定して割り切るという、『小さな問題に分割して考えて、それらを組み合わせる』といった考え方は、計算を再利用することができ、計算量が膨大に上昇することもなく最適なアルゴリズムになります。
区間DPで解くアイデア
そもそも区間DPとは?
- DP(Dyanamic Programming)の一種で、「左右の境界」という概念を持って状態を表します。
- 区間 [i, j] など「左右の端」を持つ形で部分問題を考え、それらを組み合わせて全体解を得る手法です。
問題への適用
-
両端に「1」を仮想的に追加
- 風船が存在しないときは 1 と条件分岐をする手間を省くため、
arr
(拡張配列)を使用して、あらかじめ「1」を先頭と末尾に追加します。 - 例:
[3, 1, 5, 8]
→[1, 3, 1, 5, 8, 1]
- 風船が存在しないときは 1 と条件分岐をする手間を省くため、
-
dp[i][j] の定義
- 「拡張配列の区間 [i, j] にある風船をすべて割ったときの最大得点」
-
「最後に割る風船 k」 を決める
-
[i, j]
の中で 最後 に割る風船をk
とすると、その前に[i, k]
と[k, j]
は割り済み状態ということになります。
最後に割る風船を決めておくと、前後の風船を独立して考えられるため計算が楽になります。
-
得点は次のように表せます:
これを
4. 最後に
これにより、貪欲法や全探索に比べてはるかに効率的に、最適得点を求められます。
実装:Pythonコード例
def maxCoins(nums):
n = len(nums)
# 1. 両端に 1 を追加
arr = [1] + nums + [1]
# 2. dp[i][j] = 区間 [i, j] の中の風船を全部割った最大得点
dp = [[0]*(n+2) for _ in range(n+2)]
# 3. 区間の長さを「2~n+2」に伸ばしながら計算
# length=2 のとき、中間に割れる風船がないので 0 となる
for length in range(2, n+2):
for i in range(0, n+2-length):
j = i + length
# 4. 最後に割る風船 k を全探索
for k in range(i+1, j):
score = dp[i][k] + arr[i]*arr[k]*arr[j] + dp[k][j]
dp[i][j] = max(dp[i][j], score)
return dp[0][n+1]
# 動作テスト
if __name__ == "__main__":
print(maxCoins([3,1,5,8])) # 出力: 167
- 計算量:O(n^3) ですが、LeetCodeの制限なら十分完走します。
図解で流れを理解しよう
以下のようなイメージ図で、区間DPの内部を理解します。
- arr[0] と arr[5] は仮想風船(=1)
- 真ん中の
[3,1,5,8]
が実際の風船たち - この区間
[0, 5]
を割るために、「中間要素 k を最後に割る」と考える。 - さらに
[0, k]
と[k, 5]
という小さな区間に分割し、それぞれ同様の手順で最大得点を求めます。
学習用・穴あきテスト
ここでは理解度をチェックするために、穴あき形式で問題を出します。記事を読み返しながら答えを埋めてみてください。
ご指摘ありがとうございます。問題文と答えがマッチするように、より明確で分かりやすい形に修正しました。以下のように調整します。
学習用・穴あきテスト
ここでは理解度をチェックするために、穴あき形式で問題を出します。記事を読み返しながら答えを埋めてみてください。
arr
の拡張
Q1: 境界処理を簡単にするために、もともとの nums
の前後に __a__
を挿入します。
この拡張後の配列を arr
と呼びます。
以下のコードの中の__a__
と__b__
に入る数字を考えなさい
- CODE:
arr = [ __a__ ] + nums + [ __b__ ]
答えを見る
解答: arr = [1] + nums + [1]
dp[i][j]
の定義
Q2: -
dp[i][j]
は「拡張配列の区間[i, j]
内にある風船を__c__
したときの最大得点」を表します。__c__
にはいる言葉を答えなさい。
答えを見る
解答: 「すべて割ったときの最大得点」
Q3: 最後に割る風船
- 「区間
[i, j]
の風船を割り切るとき、最後に割るのは__d__
」 と仮定します。
そのとき、得点の計算式は以下のようになります:
- ここで、(_____) に入るのは
__e__
です。
上記を参考にして__d__
と__e__
に適切に解答しなさい。
答えを見る
解答:
-
__d__
=k
-
__e__
=dp[k][j]
Q4: DPの状態遷移
-
dp[i][j]
の最大得点を求めるには、区間[i, j]
の中で 「最後に割る風船」 を考えます。そのとき、次のように区間を分けることができます:
- 空欄に当てはまるものを答えてください。
答えを見る
解答:
dp[i][k] + ( arr[i] * arr[k] * arr[j] ) + dp[k][j]
まとめ
この問題を通して、以下のポイントを押さえてください:
- 拡張配列
arr
の構造とその理由 -
dp[i][j]
がどのように区間[i, j]
の最大得点を表すか - 「最後に割る風船」を決めることで、区間が独立して考えられること
- 状態遷移の数式の仕組み
まとめ
- Burst Balloonsは「割る順番」が重要な問題で、区間DPで解くのが定番。
- 貪欲法では不十分、全探索では計算量が大きすぎる。
- 両端に「1」を追加した拡張配列と「最後に割る風船 k」 の発想がカギ。
- 計算量は O(n^3) だが、実装自体はそこまで複雑でない。
もしこの記事が参考になったら、ぜひ他の区間DP問題にも挑戦してみてください。(マトリックスチェーン問題やパレンティング問題が該当します。)きっと同じ考え方が使える場面が多いはずです!また、この記事では理系・非理系問わずに、イメージ重視で Burst Balloons を解説しました。 よければ**「いいね」や「コメント」**をよろしくお願いします!是非ご自身でコーディングしてみて、穴あきテストの答え合わせもしてみてくださいね。
Discussion