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 の隣にあるので、1 × 2 × 3 = 6 を獲得し、3 は 3 を獲得します。合計で 33 です。
- 入力
- nums = [6, 1, 2, 5]
- 出力
- 108
- 説明
- 1を取り除き（6 × 1 × 2 = 12）、次に2を取り除きます。現在は6と5の間です（6 × 2 × 5 = 60）。次に5で30、6で6となり、合計で108です。
- 入力
- nums = [8]
- 出力
- 8
- 説明
- 唯一の風船には隣がなく、欠けている隣はそれぞれ1として数えるため、1 × 8 × 1 = 8となります。
発展問題
最も多くのコインを獲得できる、もう1つの爆発順も返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの風船を最初に割るか決めるとします。その風船の両隣が隣り合うことになり、左側の風船と右側の風船は引き続き互いに影響し合います。このようにして、問題を2つの小さな問題に分割できますか？
問いを逆に考え、ひと続きの区間で最後に割れる風船を選びます。それまでは壁のように動かないため、左右にある風船同士が隣り合うことはありません。最後に割れるとき、その風船の隣にあるのは、区間の両端にある2つの風船です。
numsの両端に 1 を追加します。best[left][right]を、位置leftとrightの間にある風船から得られるコインの最大数とします。間にあるすべての風船kを最後に割る風船として試します。その風船から得られるコインは、best[left][k] + best[k][right]にvals[left] × vals[k] × vals[right]を加えた数です。短い区間から長い区間の順に埋めていきます。
解説
風船を1つ割るたびに、誰が誰の隣にいるかが変わるため、最初に割った風船によって列が分割されるわけではありません。その両側が隣同士になります。ひと続きの範囲で最後に割る風船なら、列を分割します。その風船が残り、ほかの風船はすべてなくなるため、両側の範囲は独立しており、範囲を扱う区間テーブルを使えば、O(n³) で問題を解けます。
あらゆる破裂順序を試す
正しいが、最大のテストでは終わらない
考え方
風船を1つ選び、left × value × rightを獲得して取り除き、最善の合計をすべての選択肢について維持しながら、短くなった列を同じ方法で解きます。すべての順序を試すので、正解が得られます。
最初に破裂させる風船はn個から選べて、次はn-1個から選べます。以降も同様なので、順序はn!通りあり、風船が12個の場合はすでに479,001,600通りです。残っている風船の集合ごとに結果を記憶しても役に立ちません。集合は2^n個あるからです。
アルゴリズム
burstAll(row)를 작성하세요.row에 있는 풍선에서 얻을 수 있는 코인의 최댓값을 반환하고, 빈 행이면 0을 반환합니다.- 각 위치
k에 대해, 양 끝을 넘어간 경우 1을 사용하여left × row[k] × right를 얻고,row[k]를 제거한 행에 대한burstAll의 결과를 더합니다. - 모든
k에 대한 최댓값을 반환하고,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]。このパッドは割れることがなく、欠けている隣の風船の代わりになります。solve(left, right) を、両端に立っている位置の間にある風船から得られる最大コイン数とします。
この隙間で最後に割れる風船を k とします。その隙間にある他のすべての風船は、k が壁のように立っている間に割れるため、left と k の間の部分では、その部分の風船と固定された2つの境界だけが見えます。k と right の間の部分も同様です。k を割るとき、その隣はちょうど left と right です。したがって、その隙間で得られる最大値は、すべての k について、2つの部分の最大値の合計に vals[left] × vals[k] × vals[right] を加えた値の最大値です。答えは2つのパッドの間の隙間です。隙間は約 n²/2 個あり、それぞれで最大 n 個の風船を試すため、メモ化すれば O(n³) になります。
アルゴリズム
- 両端に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][k] と best[k][right] は確定しています。
[2, 4, 3] を [1, 2, 4, 3, 1] にパディングした場合、best[0][4] では各風船を最後に割る場合を試します。3を最後に割ると、best[0][3] = 30 に 1 × 3 × 1 を加えて33となり、3通りの中で最良です。
計算量はメモ化版と同じですが、単純なループでは何百万回もの関数呼び出しを省けるため、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]
落とし穴と境界ケース
- 最初の破裂を元の隣の風船と組み合わせて分割し、
nums[k-1] × nums[k] × nums[k+1]に両側の値を足す方法。隣の風船はすでに存在しない可能性があります。[2, 4, 3]では44と計算され、実際のどの順序で得られる値よりも大きくなります。 leftを小さい方から増やしながら、行ごとに表を埋める方法。その場合、k > leftに対するbest[k][right]はまだ計算されておらず、0として読み取られます。幅ごとに埋めるか、leftを大きい方から小さくしていきましょう。- メモ化テーブルで未解決の区間を0にする方法。値が0の風船だけからなる区間の値は本当に0なので、訪問するたびに再計算されます。-1を使いましょう。
- LuaとRでは、パディングされた位置は1から
mまでなので、答えはbest[1][m]です。
よくある質問3
なぜ Burst Balloons は最初ではなく最後の風船を選ぶのでしょうか？
最初の破裂の後、その両側は隣り合うため、互いに影響し合います。区間の最後の風船は、ほかの風船が破裂する間も残るため、その両側が交わることはなく、それぞれ独立した部分問題になります。その風船が破裂するとき、隣の風船が区間の境界になります。
Burst Balloons の時間計算量はどれくらいですか？
時間計算量はO(n³)、メモリ計算量はO(n²)です。ギャップは約 n²/2 個あり、それぞれで最大 n 個の風船を最後の風船として試します。風船が300個の場合、ステップ数は約 4.5 × 10^6 です。すべての順序を試すとO(n · n!)です。
バルーンを割る問題は、貪欲な順序で解けるでしょうか？
いいえ。最小の風船を最初に割ると、[2, 4, 3]では24を獲得できますが、33を獲得することも可能です。今もっとも多く得られる風船を割ると、[2, 9, 2]では42を獲得できますが、最初に2を割ると18 + 18 + 9 = 45を獲得できます。風船を割るたびに、後で割る風船の価格が変わります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxCoins(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, 4, 3]
期待される出力
33