Burst Balloons
風船が一列に並んでおり、nums として与えられます。nums[i] は風船 i に書かれた数字です。すべての風船を、好きな順番で1つずつ割ります。風船を割ると、left × nums[i] × right 枚のコインを獲得できます。ここで left と right は、その時点で風船の左右にある隣の風船の数字です。つまり、まだ列に残っている風船のうち、各方向で最も近い風船の数字です。列の端の外側に隣の風船がない場合は、1 として扱います。風船を割ると、両隣の風船が隣り合います。獲得できるコインの最大枚数を返してください。
関数
- numsinteger-array
- 風船に書かれた数字を左から右へ
- 戻り値integer
- すべての風船を割って集められるコインの最大数
制約
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- 答えは 3 × 108 未満なので、32 ビット符号付き整数に収まります。
例
- 入力
- nums = [2, 4, 3]
- 出力
- 33
- 説明
- 最初に4を割ると、2 × 4 × 3 = 24コインを獲得します。2と3が隣り合うようになったので、次に2を割ると1 × 2 × 3 = 6を獲得し、最後に残った3を割ると1 × 3 × 1 = 3を獲得します。合計で33となり、これより良い順序はありません。小さい方の2を最初に割ると、獲得できるのは最大でも24にとどまります。
- 入力
- nums = [6, 1, 2, 5]
- 出力
- 108
- 説明
- 1を取り除き（6 × 1 × 2 = 12）、次に2を取り除きます。今度は6と5の間にあります（6 × 2 × 5 = 60）。次に5を取り除きます（6 × 5 × 1 = 30）。最後に6を取り除きます（1 × 6 × 1 = 6）。合計は12 + 60 + 30 + 6 = 108です。
- 入力
- nums = [8]
- 出力
- 8
- 説明
- 唯一の風船には隣接する風船がなく、隣接する風船がない場合はそれぞれ1として数えるため、1 × 8 × 1 = 8になります。
提出時に隠しテスト+15件
発展問題
最も多くのコインを獲得できる、もう1つの破裂順序も返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの風船を最初に割るかを決めるとします。その両隣の風船が隣り合うため、その風船の左側にある風船と右側にある風船は、依然として互いに影響し合います。このようにして、問題を2つの小さな問題に分割できますか？
質問を逆に考えて、区間の中で最後に割れる風船を選びましょう。それまでは壁のように動かないため、その左側と右側にある風船が隣り合うことはありません。最後にその風船が割れるとき、その隣の風船は区間の両端にある2つの風船です。
numsの両端に1を追加します。best[left][right]を、位置leftとrightの間にある風船から得られるコインの最大数とします。間にある各風船kを最後に割る風船として試します。そのとき得られるコインは、best[left][k] + best[k][right]にvals[left] × vals[k] × vals[right]を加えた数です。短い区間から長い区間へと埋めていきます。
解説
破裂するたびに、隣り合う風船の組み合わせが変わるため、今の選択が後のすべての破裂のコストを変えます。すべての順序を試すと、n! 個の並びになります。最初に破裂する風船を考えても、列を分割できません。なぜなら、その両側が隣り合うことになるからです。一方、ある区間で最後に破裂する風船を考えると、列を分割できます。その風船は他のすべてがなくなるまでその場に残るため、左側の区間と右側の区間は独立です。これらの区間を使った区間テーブルで、O(n³)で問題を解けます。
あらゆる爆発順序を試す
正しいが、最大のテストでは終わらない
考え方
今どれか1つ風船を選んで割り、現在の隣り合う風船を使って left × value × right を獲得し、その風船を列から取り除いて、短くなった列について同じように解きます。すべての選択肢についてこれを行い、合計が最も大きくなるものを選びます。再帰関数 burstAll(row) は、まさにこれを行います。考えられるすべての順序を調べるため、答えは正しくなります。
実際のサイズでは、とても現実的ではありません。最初に割る風船は n 個の選択肢があり、2回目は n-1 個、その次はさらに少なくなります。つまり、順序の数は n! です。風船が12個の場合でも、すでに479,001,600通りあり、最大のテストでは風船が120個あります。まだ残っている風船の各集合について結果を記憶しても、2^n 個の集合があるため、解決にはなりません。
解決の糸口は、なぜ部分問題がこれほど多いのかに気づくことです。風船 k を割ると、その左側の風船と右側の風船が隣り合うため、左側で起こることは依然として右側に左右されます。次の方法では、両側が互いに影響しなくなるように、考える対象となる風船を選びます。
アルゴリズム
burstAll(row)を記述し、rowの風船から得られるコインの最大数を返します。- 各位置
kについて、両端を超えた場合は 1 を使って、隣接する値を読み取ります。 left × row[k] × rightを獲得し、row[k]を除いた行に対するburstAllの結果を加えます。- すべての
kにおける合計の最大値を返します。行が空の場合は 0 を返します。 burstAll(nums)を呼び出します。
def maxCoins(nums):
# Most coins you can still collect from the balloons in row
def burst_all(row):
top = 0
for k in range(len(row)):
left = row[k - 1] if k > 0 else 1
right = row[k + 1] if k + 1 < len(row) else 1
# Burst row[k] now, then do as well as possible with the rest
coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
top = max(top, coins)
return top
return burst_all(nums)メモを使った最後の風船での再帰
考え方
まず、両端に 1 を置きます：vals = [1] + nums + [1]。この 2 つは破裂せず、端にある欠けた隣の風船を表します。次に、まだ残っている 2 つの位置 left と right の間の隙間に注目し、その中のどの風船が最後に破裂するかを考えます。
それが k だとします。隙間にあるほかの風船が破裂している間、k はそこに残り、壁のように風船の間に立っています。left と k の間にある風船は、その範囲内だけで隣り合い、left と k が固定された境界になります。k と right の間でも同じです。つまり、この 2 つの範囲は同じ種類の独立した問題です。k が最後に破裂すると、境界の間にあったものはすべてなくなっているため、隣はちょうど left と right になり、vals[left] × vals[k] × vals[right] のコインを獲得します。最初に破裂する風船を選んでも、このような分割はできません。両側が隣り合うことになるからです。
これを再帰で表せます。solve(left, right) は、left と right の間にある風船から得られる最大のコイン数を返します。隙間が空なら 0 を返し、そうでなければ、隙間にあるすべての k について solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] を計算し、その最大値を返します。答えは、2 つの端のパッドの間の隙間である solve(0, m-1) です。
そのままでは再帰の中で同じ隙間を何度も扱うため、それぞれの結果をテーブル memo[left][right] に保存し、次に訪れたときはその値を返します。隙間はおよそ n²/2 個あり、それぞれで最大 n 個の風船を試すため、計算量は O(n³) です。0 は実際の答えになり得るため、まだ解いていない隙間には -1 を使います。各呼び出しで扱う隙間は狭くなるので、再帰の深さは最大でも n+1 回です。
アルゴリズム
- 両端にそれぞれ 1 を追加した
numsとしてvalsを作成し、その長さをmに設定します。 - -1 で埋めた
m × mのメモ配列を作成します。 solve(left, right)を作成します。right - left < 2の場合は 0 を返し、保存済みの値があればそれを返します。- それ以外の場合は、両者の間にある各
kを最後に割る風船として試し、solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]の最大値を保持して保存します。 solve(0, m-1)を返します。
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
memo = [[-1] * m for _ in range(m)]
# Most coins from the balloons strictly between left and right
def solve(left, right):
if right - left < 2:
return 0
if memo[left][right] >= 0:
return memo[left][right]
top = 0
for last in range(left + 1, right):
# last bursts after every other balloon in the gap
coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
top = max(top, coins)
memo[left][right] = top
return top
return solve(0, m - 1)幅で区間テーブルを埋める
考え方
再帰では、常により狭い区間についてのみ尋ねます。そのため、狭い区間から広い区間へ順に埋めれば、再帰を使わずに同じ表を埋められます。best[left][right]を、leftとrightの間にある風船から得られるコインの最大数とします。間に何もない区間では0です。幅2から順に、幅がその値の各区間について、内部にあるすべてのkを最後に割る風船として試します。best[left][k]とbest[k][right]はより狭い区間なので、すでに確定しています。
[2, 4, 3]を考えてみましょう。端に値を追加すると、位置0から4までのvals = [1, 2, 4, 3, 1]となり、答えはbest[0][4]です。最も狭い区間から順に埋めていきます。
- 幅2、内部に風船が1つ：
best[0][2] = 1 × 2 × 4 = 8、best[1][3] = 2 × 4 × 3 = 24、best[2][4] = 4 × 3 × 1 = 12。 best[0][3]、風船2と4：2を最後に割ると0 + 24 + 1 × 2 × 3 = 30、4を最後に割ると8 + 0 + 1 × 4 × 3 = 20です。したがって30です。best[1][4]、風船4と3：4を最後に割ると0 + 12 + 2 × 4 × 1 = 20、3を最後に割ると24 + 0 + 2 × 3 × 1 = 30です。したがって30です。best[0][4]、3つすべて：2を最後に割ると0 + 30 + 1 × 2 × 1 = 32、4を最後に割ると8 + 12 + 1 × 4 × 1 = 24、3を最後に割ると30 + 0 + 1 × 3 × 1 = 33です。したがって33です。
最適な選択をたどると、順序がわかります。3を最後に割り、その前に左側の区間の最後として2を割り、4を最初に割ります。つまり、24 + 6 + 3 = 33です。
計算量はメモ化再帰の場合と同じです。風船が300個の場合、302 × 301 × 300 / 6 ≈ 4.5 × 10^6ステップで、302 × 302個の数値を格納する表を使います。通常のループを使えば何百万回もの関数呼び出しを避けられるため、この方法はPythonやRなどの言語での再帰より数倍高速です。
アルゴリズム
- 両端にそれぞれ 1 を追加して
numsからvalsを作り、mをその長さに設定します。 - すべて 0 で埋めた
m × mの表bestを作ります。 - 幅を 2 から
m-1まで変え、配列内でright = left + widthとなる各leftについて、その間にあるすべてのkを試します。 best[left][right]を、best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]の最大値に設定します。best[0][m-1]を返します。
def maxCoins(nums):
# A 1 on each side stands for the ends of the row
vals = [1] + nums + [1]
m = len(vals)
# best[left][right]: most coins from the balloons strictly between left and right
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
edge = vals[left] * vals[right]
top = 0
for last in range(left + 1, right):
# last goes after every other balloon in the gap,
# so left and right are its neighbours when it bursts
coins = best[left][last] + best[last][right] + edge * vals[last]
if coins > top:
top = coins
best[left][right] = top
return best[0][m - 1]
落とし穴と境界ケース
よくある間違いは、貪欲な順序、最初に破裂させる風船を基準にした再帰、誤ったメモ化マーカー、そしてテーブルを誤った順序で埋めることです。
- 貪欲な順序ではうまくいきません。最小の風船を最初に破裂させると、
[2, 4, 3]では33ではなく24になり、今すぐ最も多くの得点をもたらす風船を破裂させると、[2, 9, 2]では42になります。一方、2を最初に破裂させると18 + 18 + 9 = 45になります。 - 元の隣の風船を使って最初に破裂させる風船を基準に分割し、
nums[k-1] × nums[k] × nums[k+1]に左右の部分の値を足すと、すでに消えている可能性のある隣の風船を数えてしまいます。[2, 4, 3]では44と計算され、実際にどの順序で破裂させても得られる値を上回ります。 - 境界を隙間の一部として数えること。隙間の中をすべて破裂させた後も
leftとrightは残っています。破裂するのは、その間にある風船だけです。 leftを増やしながらテーブルを行ごとに埋めること。この場合、k > leftのときbest[k][right]はまだ計算されておらず、0として読み取られます。幅ごとに埋めるか、leftを減らしながら進めましょう。- 未解決の隙間をメモ化で0として示すこと。風船がすべて0の隙間の値は実際に0なので、いつまでも未解決に見え、訪れるたびに再計算されます。-1を使いましょう。
- 両端に追加する2つの1を忘れると、端の風船に掛け合わせる隣の風船がなくなります。
- LuaとRでは、パディングした位置は1から
mまでなので、答えはbest[1][m]です。
よくある質問4
なぜ Burst Balloons では最初の風船ではなく最後の風船を選ぶのでしょうか？
最初の風船が割れると、その両隣にあった風船が隣り合うため、左側と右側は依然として互いに影響し合い、別々に解くことはできません。ある区間の最後の風船は、ほかの風船が割れる間もその場に残るため、左右の側が接することはありません。その風船が割れるとき、その両隣は区間の固定された境界になります。これにより、各区間は独立した部分問題となり、動的計画法に適した形になります。
Burst Balloons の時間計算量はどのくらいですか？
区間テーブルにはおよそ n²/2 個の隙間があり、それぞれで最後の風船として最大 n 個を試すため、時間計算量は O(n³)、メモリ計算量は O(n²) です。風船が 300 個の場合、これは約 4.5 × 10^6 ステップです。すべての順序を試すと O(n · n!) になります。
風船を割る問題は、貪欲な順序で解けるでしょうか？
いいえ。単純なルールはどれも、短い配列で失敗します。最小の風船を最初に割ると、[2, 4, 3]では24点になりますが、33点を獲得できます。今すぐ最も多くの点を得られる風船を割ると、[2, 9, 2]では42点になりますが、先に2を割れば45点を獲得できます。風船を割ると、後で割る風船の得点が変わるため、隙間に対する動的計画法が必要です。
なぜ配列の両端に1を追加するのでしょうか？
隣接する風船がない場合は1として数えるため、値が1で決して割れない2つのパディング用風船を置くと、特別な場合分けをしなくても、実際の各風船には2つの隣接する風船ができます。また、この2つは問題全体の境界としても機能します。答えは2つのパディング用風船の間の区間、best[0][m-1]です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def maxCoins(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [2, 4, 3]
期待値
33