Interval-DP-patroon en vulvolgorde
Definieer de interval-DP-toestand dp[i][j], leg uit waarom intervallen in volgorde van toenemende lengte moeten worden gevuld en doorloop het patroon aan de hand van matrix chain multiplication.
Interval-DP-patroon en vulvolgorde is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat is interval-DP?
Interval-DP is een patroon voor dynamisch programmeren waarbij de toestand dp[i][j] het optimale antwoord voor het deelprobleem over de indices i tot en met j voorstelt. Het belangrijkste inzicht is dat we eerst kleinere intervallen oplossen en die opbouwen tot het volledige bereik. Dit patroon modelleert van nature problemen zoals matrixketenvermenigvuldiging, palindroompartitionering en ballonnen laten barsten, waarbij de grenzen van het deelprobleem de linker- en rechteruiteinden van een bereik zijn.
Definitie van de toestand en basisgevallen
Bij interval-DP is de toestand dp[i][j], waarbij i <= j. De basisgevallen zijn intervallen met één element: dp[i][i]. Deze zijn triviaal op te lossen — één matrix heeft bijvoorbeeld vermenigvuldigingskosten van nul. Intervallen met twee elementen, dp[i][i+1], hebben vaak ook eenvoudige oplossingen. We vullen de tabel in voor oplopende intervallengtes, van lengte 1 tot en met 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 intervalsVulvolgorde: oplopende lengte
Het cruciale detail bij interval-DP is de vulvolgorde. We moeten alle intervallen met lengte L berekenen voordat we intervallen met lengte L+1 berekenen, omdat een langer interval afhankelijk is van kortere deelintervallen. De buitenste lus loopt over de intervallengte van 2 tot n, de middelste lus stelt de linkergrens i in en we leiden de rechtergrens af als j = i + L - 1.
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])Voorbereiding van matrixketenvermenigvuldiging
Het klassieke interval-DP-probleem is matrixketenvermenigvuldiging: gegeven matrices met dimensies dims[0..n], vind je het minimale aantal scalaire vermenigvuldigingen om het product te berekenen. Het vermenigvuldigen van matrix A(p×q) met B(q×r) kost p*q*r bewerkingen. dp[i][j] = de minimale kosten om matrices i tot en met j te vermenigvuldigen. Het splitsingspunt k bepaalt waar de reeks in twee deelketens wordt gesplitst.
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])) # 4500De DP-tabel doorlopen
Laten we het matrixketenvoorbeeld met dimensies [10, 30, 5, 60] doorlopen. Dit stelt drie matrices voor: A(10×30), B(30×5) en C(5×60). Voor dp[0][2] proberen we te splitsen bij k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, en bij k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Dus dp[0][2] = 4500, bereikt door eerst AB te vermenigvuldigen.
Waarom deze vulvolgorde werkt
Bij het berekenen van dp[i][j] verwijzen we voor elke k in [i, j-1] naar dp[i][k] en dp[k+1][j]. Beide deelintervallen hebben een strikt kleinere lengte dan [i, j]. Door de lengte van klein naar groot te doorlopen, zijn alle benodigde deelintervallen berekend voordat we ze nodig hebben. Dit is het fundamentele correctheidsargument voor de vulvolgorde van interval-DP — kortere intervallen zijn altijd afhankelijkheden van langere intervallen.
Interval-DP van boven naar beneden met memoization
Je kunt interval-DP ook top-down met memoization implementeren. We schrijven een recursieve functie solve(i, j) die de optimale kosten voor interval [i, j] teruggeeft en slaan de resultaten op in een woordenboek. De vulvolgorde wordt automatisch door de recursie afgehandeld. Top-down is vaak gemakkelijker te begrijpen, maar kan overhead door functieaanroepen veroorzaken; bottom-up is in de praktijk sneller voor grote invoer.
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])) # 4500Tijds- en ruimtecomplexiteit
Interval-DP heeft O(n²) toestanden (alle paren (i, j)) en elke toestand doorloopt O(n) splitsingspunten, wat in totaal O(n³) tijd oplevert. De ruimte is O(n²) voor de DP-tabel. Bij matrixketenvermenigvuldiging met 100 matrices zijn dit 1.000.000 bewerkingen — zeer goed haalbaar. Het patroon komt voor in veel moeilijke LeetCode-problemen en is geliefd bij FAANG-sollicitatiegesprekken vanwege de niet voor de hand liggende structuur.
De optimale oplossing reconstrueren
Om de daadwerkelijke haakjesplaatsing te reconstrueren, en niet alleen de kosten, sla je een aparte tabel split[i][j] op waarin je vastlegt welke k bij elke toestand het minimum opleverde. Lees de splitsingen daarna recursief uit: reconstruct(i, j) toont de optimale groepering door recursief verder te gaan met [i, split[i][j]] en [split[i][j]+1, j]. Deze techniek is toepasbaar op alle interval-DP-problemen.
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], splitSjabloon voor elk interval-DP-probleem
Het universele interval-DP-sjabloon bestaat uit drie onderdelen: (1) initialiseer de basisgevallen voor afzonderlijke elementen, (2) doorloop oplopende lengtes en doorloop voor elke lengte de geldige linkergrenzen, waarbij je de rechtergrens berekent, en (3) doorloop voor elk interval alle splitsingspunten en pas de probleem-specifieke recursieformule toe. Het enige dat per probleem verandert, is de recursieformule in de binnenste lus.
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]Veelvoorkomende interval-DP-problemen
Problemen die interval-DP gebruiken zijn onder andere: Matrixketenvermenigvuldiging (bewerkingen minimaliseren), Ballonnen laten barsten (munten maximaliseren), Vreemde printer (afdrukbewerkingen minimaliseren), Triangulatie van een veelhoek met minimale score en Palindroompartitionering II. Elk probleem gebruikt dezelfde basisstructuur voor de vulvolgorde, maar een andere recursieformule. Herken het patroon wanneer een probleem vraagt om een optimale waarde over een bereik of reeks die op elk inwendig punt kan worden gesplitst.
Korte controle
Test je begrip van de concepten uit deze les van Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les leerde je: interval-DP gebruikt dp[i][j] om het optimale antwoord over een bereik voor te stellen, de vulvolgorde moet een oplopende intervallengte volgen, zodat deelintervallen eerst worden berekend, en het universele sjabloon O(n³) tijd en O(n²) ruimte gebruikt. Hierna verkennen we met precies dit patroon de langste palindromische deelrij en deelstring.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Interval-DP-patroon en vulvolgorde” gratis?
Ja — de volledige tekst van “Interval-DP-patroon en vulvolgorde” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Interval-DP-patroon en vulvolgorde”?
Definieer de interval-DP-toestand dp[i][j], leg uit waarom intervallen in volgorde van toenemende lengte moeten worden gevuld en doorloop het patroon aan de hand van matrix chain multiplication. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Interval-DP-patroon en vulvolgorde”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Interval-DP-patroon en vulvolgorde
- Langste palindromische subsequence en substring
- Palindrome Partitioning II
- Burst Balloons: interval-DP in omgekeerde richting