Burst Balloons

+10

Eine Reihe von Ballons ist als nums gegeben, wobei nums[i] die Zahl auf Ballon i ist. Du lässt alle Ballons platzen, einen nach dem anderen, in beliebiger Reihenfolge. Für einen Ballon erhältst du left × nums[i] × right Münzen, wobei left und right die Zahlen auf seinen aktuellen Nachbarn sind: den nächstgelegenen Ballons auf jeder Seite, die sich noch in der Reihe befinden. Ein fehlender Nachbar hinter einem der beiden Enden der Reihe zählt als 1. Nach dem Platzen werden die beiden Nachbarn benachbart. Gib die maximale Anzahl an Münzen zurück, die du sammeln kannst.

Funktion

maxCoins(nums: integer-array) → integer

numsinteger-array: die Zahlen auf den Luftballons, 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 ≤ 300
0 ≤ nums[i] ≤ 100
Die Antwort ist kleiner als 3 × 10⁸ und passt daher in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [2, 4, 3]
Ausgabe: 33
Erklärung: Entferne zuerst die 4 und erhalte 2 × 4 × 3 = 24 Münzen. Die 2 und die 3 sind nun Nachbarn, also erhältst du für das Entfernen der 2 1 × 2 × 3 = 6, und die 3, nun allein, bringt 1 × 3 × 1 = 3. Das ergibt 33, und keine andere Reihenfolge ist besser: Wenn du zuerst die kleine 2 entfernst, kommst du bereits höchstens auf 24.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch eine Reihenfolge zurückgeben, die möglichst viele Münzen einbringt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jeder Burst verändert, wer neben wem steht, sodass eine Entscheidung jetzt den Preis jedes späteren Bursts verändert. Alle Reihenfolgen auszuprobieren bedeutet n! Folgen. Über den ersten Ballon nachzudenken, der zerplatzt, teilt die Reihe ebenfalls nicht, denn seine beiden Seiten werden zu Nachbarn. Wenn man stattdessen über den letzten Ballon nachdenkt, der in einem Abschnitt zerplatzt, funktioniert es: Er bleibt an seinem Platz, während alle anderen verschwinden, sodass der Abschnitt links von ihm und der Abschnitt rechts von ihm unabhängig sind. Eine Intervalltabelle über diese Abschnitte löst das Problem in O(n³).

Probiere jede Reihenfolge des Zerplatzens aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Wähle jetzt einen beliebigen Ballon aus, um ihn platzen zu lassen, sammle mit seinen aktuellen Nachbarn left × value × right, entferne ihn aus der Reihe und löse die kürzere Reihe auf dieselbe Weise. Tu das für jede Möglichkeit und behalte die höchste Summe. Eine rekursive Funktion burstAll(row) macht genau das. Sie probiert jede mögliche Reihenfolge aus, daher ist die Antwort korrekt.

Für realistische Größen ist das aussichtslos. Beim ersten Ballon gibt es n Möglichkeiten, beim zweiten n-1 und so weiter: insgesamt n! Reihenfolgen. Bei 12 Ballons sind das bereits 479,001,600 Reihenfolgen, und der größte Test enthält 120 Ballons. Ergebnisse für jede Menge der noch stehenden Ballons zu speichern, hilft auch nicht, denn es gibt 2^n solcher Mengen.

Der Ausweg besteht darin, zu erkennen, warum es so viele Teilprobleme gibt. Nachdem du Ballon k platzen lässt, berühren sich der Ballon links davon und der rechts davon, sodass das Geschehen auf der linken Seite weiterhin von der rechten Seite abhängt. Beim nächsten Ansatz wählst du den Ballon, über den du nachdenkst, so aus, dass die beiden Seiten einander nicht mehr beeinflussen.

Algorithmus

Schreibe burstAll(row), das die meisten Münzen aus den Ballons in row zurückgibt.
Lies für jede Position k die Nachbarn aus und verwende an beiden Enden den Wert 1.
Verdiene left × row[k] × right und addiere das Ergebnis von burstAll für die Zeile ohne row[k].
Gib die beste Gesamtsumme für alle k zurück oder 0 für eine leere Zeile.
Rufe burstAll(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 Memo

Idee

Füge zuerst an beiden Enden eine 1 ein: vals = [1] + nums + [1]. Diese beiden platzen nie und stehen für die fehlenden Nachbarn an den Rändern. Betrachte nun eine Lücke zwischen zwei Positionen left und right, die beide noch stehen, und frage dich: Welcher Ballon innerhalb der Lücke platzt zuletzt?

Nehmen wir an, es ist k. Während die anderen Ballons in der Lücke platzen, ist k noch da und steht wie eine Wand zwischen ihnen. Jeder Ballon zwischen left und k hat nur Nachbarn aus diesem Abschnitt, wobei left und k feste Grenzen sind. Dasselbe gilt zwischen k und right. Die beiden Abschnitte sind also unabhängige Probleme derselben Art. Wenn k schließlich platzt, ist alles zwischen den Grenzen verschwunden. Seine Nachbarn sind dann genau left und right, und es bringt vals[left] × vals[k] × vals[right] Münzen ein. Den ersten Ballon zu wählen, ergibt keine solche Aufteilung, weil seine beiden Seiten zu Nachbarn werden.

Das ergibt eine Rekursion. solve(left, right) gibt die maximale Münzanzahl der Ballons zurück, die sich strikt zwischen left und right befinden: 0, wenn die Lücke leer ist, andernfalls das Maximum von solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] für jedes k in der Lücke. Die Antwort ist solve(0, m-1), also die Lücke zwischen den beiden Randballons.

Für sich genommen betrachtet die Rekursion dieselbe Lücke immer wieder. Speichere daher jedes Ergebnis in einer Tabelle memo[left][right] und gib es bei einem erneuten Aufruf zurück. Es gibt ungefähr n²/2 Lücken, für jede werden bis zu n Ballons ausprobiert. Daher beträgt der Aufwand O(n³). Verwende -1 für eine noch nicht gelöste Lücke, da 0 eine gültige Antwort ist. Die Rekursion geht nie tiefer als n+1 Aufrufe, weil jeder Aufruf mit einer engeren Lücke arbeitet.

Algorithmus

Erstelle vals aus nums, indem du an beiden Enden eine 1 hinzufügst, und setze m auf seine Länge.
Erstelle ein m × m-Memo, das mit -1 gefüllt ist.
Schreibe solve(left, right): Gib 0 zurück, wenn right - left < 2, und den gespeicherten Wert, falls vorhanden.
Probiere andernfalls jedes k strikt zwischen ihnen als letzten Ballon aus, behalte den größten Wert von solve(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 immer nur nach kleineren Abständen. Du kannst also dieselbe Tabelle auch ohne Rekursion füllen, solange du schmale Abstände vor breiten füllst. Sei best[left][right] die maximale Anzahl Münzen aus den Ballons strikt zwischen left und right, 0 bei einem Abstand ohne Ballons. Probiere für jede Breite ab 2 und für jeden Abstand dieser Breite jedes k darin als letzten Ballon aus. best[left][k] und best[k][right] sind schmaler und daher bereits endgültig berechnet.

Nimm [2, 4, 3]. Mit Auffüllung ergibt sich vals = [1, 2, 4, 3, 1] an den Positionen 0 bis 4, und die Antwort ist best[0][4]. Fülle die Abstände vom schmalsten zum breitesten:

Breite 2, ein Ballon dazwischen: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], Ballons 2 und 4: Ist die 2 zuletzt dran, ergibt sich 0 + 24 + 1 × 2 × 3 = 30; ist die 4 zuletzt dran, ergibt sich 8 + 0 + 1 × 4 × 3 = 20. Also 30.
best[1][4], Ballons 4 und 3: Ist die 4 zuletzt dran, ergibt sich 0 + 12 + 2 × 4 × 1 = 20; ist die 3 zuletzt dran, ergibt sich 24 + 0 + 2 × 3 × 1 = 30. Also 30.
best[0][4], alle drei: Ist die 2 zuletzt dran, ergibt sich 0 + 30 + 1 × 2 × 1 = 32; ist die 4 zuletzt dran, ergibt sich 8 + 12 + 1 × 4 × 1 = 24; ist die 3 zuletzt dran, ergibt sich 30 + 0 + 1 × 3 × 1 = 33. Also 33.

Wenn du die gewählten Ballons zurückverfolgst, erhältst du diese Reihenfolge: Die 3 kommt zuletzt, davor ist die 2 im Abschnitt links davon die letzte, und die 4 kommt zuerst. Das ergibt 24 + 6 + 3 = 33.

Der Aufwand ist derselbe wie bei der Memoisierung: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 Schritte für 300 Ballons und eine Tabelle mit 302 × 302 Zahlen. Einfache Schleifen vermeiden Millionen von Funktionsaufrufen, wodurch diese Version in einer Sprache wie Python oder R um ein Mehrfaches schneller ist als die Rekursion.

Algorithmus

Erstelle vals als nums mit einer am Anfang und am Ende hinzugefügten 1 und setze m auf dessen Länge.
Erstelle eine m × m-Tabelle best, die mit 0 gefüllt ist.
Probiere für jede Breite von 2 bis m-1 und jedes left mit right = left + width innerhalb des Arrays jedes k strikt zwischen ihnen aus.
Setze best[left][right] auf den größten Wert aus best[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

Die üblichen Fehler sind eine gierige Reihenfolge, eine Rekursion über den ersten Ballon, der platzt, ein ungeeigneter Memoisierungsmarker und eine Tabelle, die in der falschen Reihenfolge ausgefüllt wird.

Gierige Reihenfolgen schlagen fehl. Wenn man den kleinsten Ballon zuerst platzen lässt, erhält man bei [2, 4, 3] 24 statt 33. Lässt man den Ballon platzen, der gerade den höchsten Ertrag bringt, erhält man bei [2, 9, 2] 42, während das Platzenlassen einer 2 zuerst 18 + 18 + 9 = 45 ergibt.
Wenn man beim ersten platzenden Ballon mit seinen ursprünglichen Nachbarn aufteilt, also nums[k-1] × nums[k] × nums[k+1] plus die beiden Seiten rechnet, zählt man Nachbarn mit, die möglicherweise bereits geplatzt sind. Bei [2, 4, 3] ergibt das 44, mehr als jede tatsächlich mögliche Reihenfolge einbringt.
Die Ränder als Teil der Lücke mitzuzählen. left und right bleiben stehen, wenn die Lücke geleert wird; nur die Ballons, die sich strikt zwischen ihnen befinden, platzen.
Die Tabelle zeilenweise auszufüllen, während left aufsteigt. Dann ist best[k][right] für k > left noch nicht berechnet und wird als 0 gelesen. Fülle die Tabelle nach Breite aus oder gehe left abwärts durch.
Eine ungelöste Lücke im Memo mit 0 zu markieren. Eine Lücke voller Ballons mit Wert 0 ist tatsächlich 0 wert, sieht also für immer ungelöst aus und wird bei jedem Besuch erneut gelöst. Verwende -1.
Die beiden Auffüll-1en zu vergessen, sodass die Randballons keinen Nachbarn haben, mit dem sie multipliziert werden können.
In Lua und R laufen die aufgefüllten Positionen von 1 bis m, daher lautet die Antwort best[1][m].

Häufige Fragen4

Warum wählt Burst Balloons den letzten Ballon statt des ersten?

Nach dem ersten Platzen werden die Ballons auf beiden Seiten zu Nachbarn, sodass der linke und der rechte Teil sich weiterhin gegenseitig beeinflussen und nicht getrennt gelöst werden können. Der letzte Ballon eines Abschnitts bleibt an Ort und Stelle, während die anderen platzen, sodass die beiden Seiten nie aufeinandertreffen. Wenn er platzt, sind seine Nachbarn die festen Grenzen des Abschnitts. Dadurch wird jeder Abschnitt zu einem unabhängigen Teilproblem, und genau das braucht die dynamische Programmierung.

Wie hoch ist die Zeitkomplexität von Burst Balloons?

Die Intervalltabelle hat etwa n²/2 Lücken, und für jede werden bis zu n Ballons als letzter ausprobiert. Daher beträgt die Laufzeit O(n³) und der Speicherbedarf O(n²). 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 Greedy-Reihenfolge lösen?

Nein. Jede einfache Regel scheitert bereits bei einer kurzen Reihe. Wenn man zuerst den kleinsten Ballon platzen lässt, erhält man bei [2, 4, 3] 24, obwohl 33 möglich sind. Wenn man den Ballon platzen lässt, der gerade am meisten einbringt, erhält man bei [2, 9, 2] 42, obwohl man 45 erhält, wenn man zuerst eine 2 platzen lässt. Wenn ein Ballon platzt, ändern sich die Preise der späteren Ballons. Daher brauchst du die dynamische Programmierung über Lücken.

Warum eine 1 an beiden Enden des Arrays hinzufügen?

Ein fehlender Nachbar zählt als 1, sodass zwei Polsterballons mit dem Wert 1, die nie platzen, jedem echten Ballon zwei Nachbarn geben, ohne dass Sonderfälle nötig sind. Sie bilden außerdem die Begrenzungen des gesamten Problems: Die Antwort ist die Lücke zwischen den beiden Polstern, best[0][m-1].

Python

def maxCoins(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [2, 4, 3]

Erwartet

Burst Balloons

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Reihenfolge des Zerplatzens aus

Rekursion beim letzten Ballon mit Memo

Fülle die Intervalltabelle nach Breite aus

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben