Burst Balloons: Umgekehrte Intervall-DP

Gegeben seien n Ballons mit den Werten nums. Wenn Ballon i zerplatzt, erhalten Sie nums[i-1] * nums[i] * nums[i+1] Münzen, also das Produkt aus seinem eigenen Wert und den Werten seiner aktuellen Nachbarn. Nach dem Zerplatzen werden die Nachbarn benachbart. Finden Sie die maximale Anzahl an Münzen, die Sie durch das Zerplatzen aller Ballons sammeln können. Eine naive Simulation ist schwierig, da sich beim Zerplatzen die Nachbarn ändern – umgekehrte Intervall-DP umgeht diese Schwierigkeit elegant.

Wenn wir dp[i][j] als maximale Münzanzahl beim Zerplatzen der Ballons im Bereich [i, j] definieren und überlegen, welchen Ballon wir zuerst zerplatzen lassen, entsteht ein Problem: Wenn Ballon k zuerst zerplatzt, müssen nums[k-1] und nums[k+1] seine aktuellen Nachbarn sein – diese Ballons könnten jedoch später zerplatzen, wodurch sich die Nachbarn dynamisch ändern. Der Zustand lässt sich in Vorwärtsrichtung nur schwer sauber definieren.

Der Trick besteht darin, zu überlegen, welcher Ballon im Intervall [i, j] als Letzter zerplatzt. Wenn Ballon k im Intervall [i, j] als Letzter zerplatzt, sind alle anderen Ballons in [i, j] bereits verschwunden. Die Nachbarn von Ballon k sind dann genau nums[i-1] und nums[j+1] – die Randballons direkt außerhalb des Intervalls. Dadurch ist die Münzberechnung für den letzten Zerplatzvorgang deterministisch: Sie hängt nicht von der Reihenfolge der vorherigen Zerplatzvorgänge ab.

Fügen Sie Sentinel-Ballons hinzu: Stellen Sie nums = [1] + nums + [1] her, indem Sie an nums vorne und hinten eine 1 anfügen. Definieren Sie dp[i][j] als die maximale Münzanzahl, die Sie erhalten, wenn Sie alle Ballons strikt zwischen den Indizes i und j zerplatzen lassen (exklusiv), wobei nums[i] und nums[j] die verbleibenden Randballons sind. Rekurrenz: Für jeden möglichen letzten Ballon k in (i, j) gilt: dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Wir erweitern das Array um Sentinel-Werte, initialisieren die DP-Tabelle mit Nullen (leeres Intervall = 0 Münzen) und füllen sie für Intervalle mit zunehmender Länge. Die endgültige Antwort ist dp[0][n+1] und stellt die maximale Münzanzahl dar, die sich durch das Zerplatzen aller ursprünglichen Ballons mit den Sentinels als unveränderlichen Grenzen erzielen lässt.

Für [3, 1, 5, 8], erweitert zu [1, 3, 1, 5, 8, 1] (Indizes 0–5). Gesucht ist dp[0][5]. Für Intervalle mit length=2 (ein Ballon im Inneren) gilt: dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. Durch schrittweises Aufbauen ergibt sich als Optimum, die 1 aus {3,1,5,8} zuletzt zerplatzen zu lassen, nachdem die Nachbarn zuerst zerplatzt wurden; dadurch erhält man insgesamt 167 Münzen.

Es gibt O(n²) Intervalle, und für jedes Intervall probieren wir O(n) Teilungspunkte aus. Daraus ergibt sich eine Zeitkomplexität von O(n³). Der Speicherbedarf für die DP-Tabelle beträgt O(n²). Für n = 500 Ballons sind das 125 Millionen Operationen – für typische Interview-Grenzen machbar. Das Auffüllen mit Sentinels vereinfacht die Behandlung der Randfälle: Ohne sie müssten Sie explizit prüfen, ob i-1 und j+1 innerhalb der Grenzen liegen.

Dieselbe Lösung kann mit @lru_cache als Top-down-Ansatz geschrieben werden, was sich während eines Interviews möglicherweise intuitiver herleiten lässt. Definieren Sie solve(i, j) als die maximale Münzanzahl im offenen Intervall (i, j). Die Funktion probiert alle k als letzten Zerplatzvorgang aus und memoisiert die Ergebnisse. Beide Ansätze haben dieselbe Zeit- und Speicherkomplexität.

Ein häufiger Fehler besteht darin, dp[i][j] als Münzanzahl zu definieren, wenn der erste Ballon in [i,j] zerplatzt, statt den letzten zu betrachten. Dies scheitert, weil die Münzberechnung für den ersten Zerplatzvorgang von Nachbarballons abhängt, die noch nicht zerplatzt sind – und sich der Zustand dieser Nachbarn im Verlauf des Algorithmus ändert. Denken Sie bei Intervall-DP immer an das letzte Element, wenn die Grenzen von den verbleibenden Elementen abhängen.

Sentinels mit dem Wert 1 werden gewählt, weil sie als neutrale Elemente für die Multiplikation fungieren. Wenn ein Randballon als Letzter zerplatzt, beträgt sein Münzwert boundary * last * boundary = 1 * last * 1 = last. Der Wert 0 würde 0 Münzen ergeben (falsch), andere Werte würden die Berechnung verfälschen. Der Sentinel-Trick vereinheitlicht alle Randfälle, ohne den Ballon ganz links und den ganz rechts gesondert behandeln zu müssen.

Bei standardmäßiger Intervall-DP (Matrix Chain) bezeichnet der Teilungspunkt k die Stelle, an der wir das Problem in zwei unabhängig gelöste Teilprobleme aufteilen. Bei Burst Balloons ist k der Ballon, der im Intervall als Letzter zerplatzt. Dadurch sind die beiden Teilintervalle [i,k] und [k,j] unabhängig, solange k noch als Grenze vorhanden ist. Diese umgekehrte Perspektive ist die entscheidende kreative Erkenntnis, die es ermöglicht, Burst Balloons mit Intervall-DP zu lösen.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie gelernt: Die Vorwärtssimulation scheitert, weil das Platzen von Ballons die Nachbarn unvorhersehbar verändert, die umgekehrte Erkenntnis definiert k als den zuletzt platzenden Ballon in einem Intervall, wodurch nums[i] und nums[j] zu Nachbarn werden, und die Rekurrenz dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) mit Sentinel-Auffüllung ermöglicht eine Lösung in O(n³). Als Nächstes wechseln wir zur Rucksack-DP, beginnend mit dem klassischen 0/1-Rucksackproblem und seiner Speicheroptimierung.