Burst Balloons
Eine Reihe von Luftballons ist als nums gegeben, wobei nums[i] die Zahl auf Luftballon i ist. Du lässt alle Luftballons platzen, einen nach dem anderen, in beliebiger Reihenfolge. Für das Platzen eines Luftballons erhältst du left × nums[i] × right Münzen, wobei left und right die Zahlen auf seinen aktuellen Nachbarn sind, also den nächstgelegenen Luftballons auf jeder Seite, die sich noch in der Reihe befinden. Ein fehlender Nachbar zählt als 1. Nach dem Platzen werden seine beiden Nachbarn benachbart. Gib die größtmögliche Anzahl an Münzen zurück, die du sammeln kannst.
Funktion
- numsinteger-array
- die Zahlen auf den Ballons, von links nach rechts
- Gibt zurückinteger
- die meisten Münzen, die du sammeln kannst, indem du jeden Ballon zum Platzen bringst
Einschränkungen
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 100- Die Antwort liegt unter 3 × 108 und passt daher in eine vorzeichenbehaftete 32-Bit-Ganzzahl.
Beispiele
- Eingabe
- nums = [2, 4, 3]
- Ausgabe
- 33
- Erklärung
- Multipliziere die 4 mit 2 × 4 × 3 = 24. Die 2 erhält, jetzt neben der 3, 1 × 2 × 3 = 6, und die 3 erhält 3: insgesamt 33.
- Eingabe
- nums = [6, 1, 2, 5]
- Ausgabe
- 108
- Erklärung
- Multipliziere die 1 (6 × 1 × 2 = 12), dann die 2, jetzt zwischen 6 und 5 (6 × 2 × 5 = 60), dann die 5 für 30 und die 6 für 6: insgesamt 108.
- Eingabe
- nums = [8]
- Ausgabe
- 8
- Erklärung
- Der einzige Ballon hat keine Nachbarn, und jeder fehlende Nachbar zählt als 1, also ergibt sich 1 × 8 × 1 = 8.
Weiterführende Frage
Kannst du außerdem eine platzende Reihenfolge zurückgeben, mit der du die meisten Münzen verdienst?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Angenommen, du entscheidest, welchen Ballon du zuerst zerplatzen lässt. Seine beiden Nachbarn liegen dann nebeneinander, sodass die Ballons links und die Ballons rechts davon weiterhin aufeinander einwirken. Kannst du das Problem auf diese Weise in zwei kleinere Probleme aufteilen?
Dreh die Frage um und wähle den Ballon, der in einem Abschnitt zuletzt platzt. Bis dahin bleibt er stehen wie eine Wand, sodass die Ballons links und rechts von ihm nie zu Nachbarn werden. Wenn er schließlich platzt, sind seine Nachbarn die beiden Ballons, die an den Abschnitt angrenzen.
Füge an beiden Enden von
numseine 1 ein. Seibest[left][right]die maximale Anzahl an Münzen, die sich mit den Ballons strikt zwischen den Positionenleftundrighterzielen lässt. Probiere jeden Ballonkdazwischen als letzten aus: Er bringtbest[left][k] + best[k][right]plusvals[left] × vals[k] × vals[right]. Fülle kurze Abstände vor langen.
Lösung
Jeder platzende Ballon verändert, wer neben wem steht. Daher teilt der zuerst platzende Ballon die Reihe nicht: Seine beiden Seiten werden zu Nachbarn. Der Ballon, der in einem Abschnitt zuletzt platzt, tut es hingegen. Er bleibt stehen, während alle anderen verschwinden, sodass die Abschnitte auf seinen beiden Seiten unabhängig sind. Eine Intervalltabelle über Abschnitte löst das Problem in O(n³).
Probiere jede Reihenfolge des Platzens aus
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Wähle einen Ballon aus, sammle left × value × right, entferne ihn und löse die kürzere Reihe auf dieselbe Weise, wobei du über alle Möglichkeiten hinweg die beste Summe behältst. Dabei werden alle Reihenfolgen ausprobiert, also ist das Ergebnis korrekt.
Beim ersten Platzenlassen gibt es n Möglichkeiten, beim nächsten n-1 und so weiter: n! Reihenfolgen, bei 12 Ballons bereits 479,001,600. Ergebnisse für jede Menge der noch stehenden Ballons zu speichern, hilft nicht, da es 2^n Mengen gibt.
Algorithmus
- Schreibe
burstAll(row), die maximale Münzanzahl aus den Ballons inrow, bei einer leeren Reihe 0. - Erziele für jede Position
kleft × row[k] × right, wobei außerhalb beider Enden 1 verwendet wird, plusburstAllfür die Reihe ohnerow[k]. - Gib die beste Summe über alle
kzurück und rufeburstAll(nums)auf.
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)Rekursion beim letzten Ballon, mit einem Memo
Idee
Fülle die Reihe an beiden Enden mit einer 1 auf: vals = [1] + nums + [1]. Die Auffüllwerte platzen nie und stehen für die fehlenden Nachbarn. Sei solve(left, right) die maximale Anzahl an Münzen, die sich mit den Ballons strikt zwischen zwei stehenden Positionen erzielen lässt.
Angenommen, k platzt zuletzt in dieser Lücke. Jeder andere Ballon darin platzt, während k wie eine Wand stehen bleibt. Daher sieht der Bereich zwischen left und k nur seine eigenen Ballons und zwei feste Grenzen, und dasselbe gilt für den Bereich zwischen k und right. Wenn k platzt, sind seine Nachbarn genau left und right. Das Optimum für die Lücke ist also für jedes k das Maximum aus den beiden Teilbereichen plus vals[left] × vals[k] × vals[right]. Die Antwort ist die Lücke zwischen den beiden Auffüllwerten. Es gibt etwa n²/2 Lücken, und jede probiert bis zu n Ballons aus. Mit Memoisierung ergibt sich also O(n³).
Algorithmus
- Erstelle
valsalsnumsmit einer an jedem Ende hinzugefügten 1 und setzemauf seine Länge. - Erstelle eine
m × m-Memo-Tabelle, die mit -1 gefüllt ist. - Schreibe
solve(left, right): return 0, wennright - left < 2, und gib den gespeicherten Wert zurück, falls vorhanden. - Probiere andernfalls jedes
kstrikt zwischen ihnen als letzten Ballon aus, behalte den größten Wert vonsolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]und speichere ihn. - Gib
solve(0, m-1)zurück.
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)Fülle die Intervalltabelle nach Breite aus
Idee
Die Rekursion fragt nur nach kleineren Abständen. Fülle daher dieselbe Tabelle mit Schleifen: erst kleine, dann große Abstände. Dann sind best[left][k] und best[k][right] bereits endgültig, wenn ein größerer Abstand sie benötigt.
Für [2, 4, 3], ergänzt zu [1, 2, 4, 3, 1], probiert best[0][4] jeden Ballon als letzten aus. Wird die 3 zuletzt entfernt, ergibt best[0][3] = 30 plus 1 × 3 × 1 insgesamt 33 – den besten Wert der drei Möglichkeiten.
Der Aufwand entspricht dem der Memo-Version, aber einfache Schleifen überspringen Millionen von Funktionsaufrufen, wodurch diese Version in einer Sprache wie Python oder R um ein Mehrfaches schneller ist.
Algorithmus
- Erstelle
valsausnums, indem du an beiden Enden eine 1 hinzufügst, und setzemauf seine Länge. - Erstelle eine
m × m-Tabellebest, die mit 0 gefüllt ist. - Probiere für jede Breite von 2 bis
m-1und jedesleftmitright = left + widthinnerhalb des Arrays jedeskaus, das strikt dazwischen liegt. - Setze
best[left][right]auf den größten Wert vonbest[left][k] + best[k][right] + vals[left] × vals[k] × vals[right]. - Gib
best[0][m-1]zurück.
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]
Stolperfallen und Grenzfälle
- Beim Aufteilen beim ersten Platzen mit den ursprünglichen Nachbarn,
nums[k-1] × nums[k] × nums[k+1]plus den beiden Seiten. Diese Nachbarn können bereits verschwunden sein: Bei[2, 4, 3]ergibt sich 44, mehr als bei jeder tatsächlichen Reihenfolge erreicht wird. - Die Tabelle zeilenweise ausfüllen, wobei
leftimmer größer wird. Dann wurdebest[k][right]fürk > leftnoch nicht berechnet und wird als 0 gelesen. Fülle die Tabelle nach Breite aus oder geheleftabsteigend durch. - Eine ungelöste Lücke im Memo mit 0 markieren. Eine Lücke mit Ballons, deren Werte 0 sind, ist tatsächlich 0 wert und wird daher bei jedem Besuch erneut gelöst. Verwende -1.
- In Lua und R reichen die aufgefüllten Positionen von 1 bis
m, daher lautet die Antwortbest[1][m].
Häufige Fragen3
Warum wählt Burst Balloons den letzten statt des ersten Ballons?
Nach dem ersten Platzen werden seine beiden Seiten zu Nachbarn, sodass sie sich weiterhin gegenseitig beeinflussen. Der letzte Ballon eines Abschnitts bleibt stehen, während die anderen platzen, sodass seine beiden Seiten nie aufeinandertreffen und jede ein unabhängiges Teilproblem ist. Wenn er platzt, sind seine Nachbarn die Grenzen des Abschnitts.
Wie hoch ist die Zeitkomplexität von Burst Balloons?
O(n³) Laufzeit und O(n²) Speicherbedarf: etwa n²/2 Lücken, wobei für jede bis zu n Ballons als letzter ausprobiert werden. Bei 300 Ballons sind das etwa 4.5 × 10^6 Schritte. Jede Reihenfolge auszuprobieren, hat eine Laufzeit von O(n · n!).
Kann man Burst Balloons mit einer gierigen Reihenfolge lösen?
Nein. Wenn du den kleinsten Ballon zuerst platzen lässt, erhältst du bei [2, 4, 3] 24, obwohl 33 möglich sind. Wenn du den Ballon platzen lässt, der jetzt am meisten einbringt, erhältst du bei [2, 9, 2] 42, obwohl das Platzen einer 2 zuerst 18 + 18 + 9 = 45 ergibt. Jeder geplatzte Ballon verändert die Preise der späteren.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def maxCoins(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [2, 4, 3]
Erwartete Ausgabe
33