Intervall-DP-Muster und Reihenfolge des Ausfüllens
Definieren Sie den Intervall-DP-Zustand dp[i][j], erklären Sie, warum Intervalle in aufsteigender Längenreihenfolge ausgefüllt werden müssen, und verfolgen Sie das Muster an der Matrixkettenmultiplikation.
Intervall-DP-Muster und Reihenfolge des Ausfüllens ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist Intervall-DP?
Intervall-DP ist ein Muster der dynamischen Programmierung, bei dem der Zustand dp[i][j] die optimale Lösung für das Teilproblem darstellt, das sich über die Indizes i bis j erstreckt. Die zentrale Erkenntnis ist, dass wir zuerst kleinere Intervalle lösen und uns zur vollständigen Spannweite vorarbeiten. Dieses Muster bildet Probleme wie Matrixkettenmultiplikation, Palindrompartitionierung und das Zerplatzen von Ballons auf natürliche Weise ab, da die Grenzen des Teilproblems durch den linken und rechten Endpunkt eines Bereichs bestimmt werden.
Zustandsdefinition und Basisfälle
Bei Intervall-DP ist der Zustand dp[i][j], wobei i <= j gilt. Die Basisfälle sind Intervalle mit einem einzigen Element: dp[i][i]. Diese sind trivial gelöst – beispielsweise verursachen einzelne Matrizen keine Multiplikationskosten. Auch Intervalle mit zwei Elementen, dp[i][i+1], haben oft einfache Lösungen. Wir füllen die Tabelle nach zunehmender Intervalllänge, beginnend bei der Länge 1 bis hin zu n.
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervalsFüllreihenfolge: zunehmende Länge
Das entscheidende Detail bei Intervall-DP ist die Füllreihenfolge. Wir müssen alle Intervalle der Länge L berechnen, bevor wir Intervalle der Länge L+1 berechnen können, weil ein längeres Intervall von kürzeren Teilintervallen abhängt. Die äußere Schleife durchläuft die Intervalllänge von 2 bis n, die mittlere Schleife legt die linke Grenze i fest, und die rechte Grenze leiten wir als j = i + L - 1 her.
n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for length in range(2, n + 1): # interval length
for i in range(n - length + 1): # left boundary
j = i + length - 1 # right boundary
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])Aufbau der Matrixkettenmultiplikation
Das klassische Intervall-DP-Problem ist die Matrixkettenmultiplikation: Gegeben sind Matrizen mit den Dimensionen dims[0..n]; gesucht ist die minimale Anzahl skalarer Multiplikationen zur Berechnung des Produkts. Die Multiplikation der Matrix A(p×q) mit B(q×r) kostet p*q*r Operationen. dp[i][j] = minimale Kosten für die Multiplikation der Matrizen von i bis j. Der Teilungspunkt k legt fest, an welcher Stelle die Folge in zwei Teilketten geteilt wird.
def matrix_chain_order(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
print(matrix_chain_order([10, 30, 5, 60])) # 4500Nachvollziehen der DP-Tabelle
Sehen wir uns das Matrixkettenbeispiel mit den Dimensionen [10, 30, 5, 60] an, das drei Matrizen repräsentiert: A(10×30), B(30×5), C(5×60). Für dp[0][2] testen wir die Aufteilung bei k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, und bei k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Also gilt dp[0][2] = 4500; dieses Ergebnis wird erreicht, indem zuerst AB multipliziert wird.
Warum diese Füllreihenfolge funktioniert
Bei der Berechnung von dp[i][j] greifen wir für jedes k in [i, j-1] auf dp[i][k] und dp[k+1][j] zu. Beide Teilintervalle haben eine streng kleinere Länge als [i, j]. Indem wir die Länge von klein nach groß durchlaufen, werden alle benötigten Teilintervalle berechnet, bevor wir sie benötigen. Das ist die grundlegende Begründung für die Korrektheit der Füllreihenfolge bei Intervall-DP – kürzere Intervalle sind immer Abhängigkeiten längerer Intervalle.
Memoisiertes Top-down-Intervall-DP
Alternativ kann Intervall-DP Top-down mit Memoisierung implementiert werden. Wir schreiben eine rekursive Funktion solve(i, j), die die optimalen Kosten für das Intervall [i, j] zurückgibt, und speichern die Ergebnisse in einem Wörterbuch. Die Füllreihenfolge wird dabei automatisch durch die Rekursion gehandhabt. Top-down ist oft leichter nachzuvollziehen, kann aber einen Funktionsaufruf-Overhead verursachen; Bottom-up ist in der Praxis bei großen Eingaben schneller.
from functools import lru_cache
def matrix_chain_memo(dims):
n = len(dims) - 1
@lru_cache(maxsize=None)
def solve(i, j):
if i == j:
return 0
return min(
solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
for k in range(i, j)
)
return solve(0, n-1)
print(matrix_chain_memo([10, 30, 5, 60])) # 4500Zeit- und Speicherkomplexität
Intervall-DP hat O(n²) Zustände (alle Paare (i, j)), und jeder Zustand durchläuft O(n) Teilungspunkte, was insgesamt eine Laufzeit von O(n³) ergibt. Der Speicherbedarf beträgt O(n²) für die DP-Tabelle. Bei der Matrixkettenmultiplikation mit 100 Matrizen entspricht das 1.000.000 Operationen – sehr gut machbar. Dieses Muster tritt in vielen schwierigen LeetCode-Problemen auf und ist wegen seiner nicht offensichtlichen Struktur ein beliebtes Thema in FAANG-Interviews.
Die optimale Lösung rekonstruieren
Um die tatsächliche Klammerung (nicht nur die Kosten) zu rekonstruieren, speichern Sie eine separate Tabelle split[i][j], die für jeden Zustand festhält, welches k das Minimum erreicht hat. Lesen Sie die Teilungen anschließend rekursiv ab: reconstruct(i, j) gibt die optimale Gruppierung aus, indem die Rekursion auf [i, split[i][j]] und [split[i][j]+1, j] angewendet wird. Diese Technik gilt für alle Intervall-DP-Probleme.
def matrix_chain_with_split(dims):
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
split = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp[0][n-1], splitVorlage für jedes Intervall-DP-Problem
Die universelle Vorlage für Intervall-DP besteht aus drei Teilen: (1) Initialisieren Sie die Basisfälle für einzelne Elemente, (2) durchlaufen Sie die zunehmenden Längen und für jede Länge die gültigen linken Grenzen, wobei Sie die rechte Grenze berechnen, und (3) durchlaufen Sie für jedes Intervall alle Teilungspunkte und wenden Sie die problemspezifische Rekurrenz an. Zwischen den Problemen ändert sich nur die Rekurrenzformel innerhalb der innersten Schleife.
def interval_dp_template(n, base_cost, split_cost):
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = base_cost(i) # problem-specific base case
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
# problem-specific recurrence
candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
dp[i][j] = min(dp[i][j], candidate)
return dp[0][n-1]Gängige Intervall-DP-Probleme
Zu den Problemen, die Intervall-DP verwenden, gehören: Matrixkettenmultiplikation (Operationen minimieren), Ballons zerplatzen lassen (Münzen maximieren), Seltsamer Drucker (Druckoperationen minimieren), Minimale Punktzahl bei der Triangulation eines Polygons und Palindrompartitionierung II. Alle verwenden dasselbe Gerüst für die Füllreihenfolge, aber unterschiedliche Rekurrenzen. Erkennen Sie dieses Muster, wenn ein Problem einen optimalen Wert für einen Bereich oder eine Folge verlangt, die an jedem inneren Punkt geteilt werden kann.
Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Intervall-DP verwendet dp[i][j], um die optimale Lösung für einen Bereich darzustellen, die Füllreihenfolge muss der zunehmenden Intervalllänge folgen, damit Teilintervalle zuerst berechnet werden, und die universelle Vorlage hat eine Laufzeit von O(n³) und einen Speicherbedarf von O(n²). Als Nächstes untersuchen wir mit diesem Muster die längste palindromische Teilfolge und den längsten palindromischen Teilstring.
Häufig gestellte Fragen
Ist die Lektion „Intervall-DP-Muster und Reihenfolge des Ausfüllens“ kostenlos?
Ja — der vollständige Text von „Intervall-DP-Muster und Reihenfolge des Ausfüllens“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Intervall-DP-Muster und Reihenfolge des Ausfüllens“?
Definieren Sie den Intervall-DP-Zustand dp[i][j], erklären Sie, warum Intervalle in aufsteigender Längenreihenfolge ausgefüllt werden müssen, und verfolgen Sie das Muster an der Matrixkettenmultiplik… Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Intervall-DP-Muster und Reihenfolge des Ausfüllens“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Intervall-DP-Muster und Reihenfolge des Ausfüllens
- Längste palindromische Teilfolge und Teilzeichenkette
- Palindrome Partitioning II
- Burst Balloons: Umgekehrte Intervall-DP