Mönstret för intervall-DP och fyllnadsordning
Definiera DP-tillståndet dp[i][j] för intervall, förklara varför intervall måste fyllas i ordning efter ökande längd och följ mönstret på matrix chain multiplication.
Mönstret för intervall-DP och fyllnadsordning är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 1 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad är intervall-DP?
Intervall-DP är ett mönster inom dynamisk programmering där tillståndet dp[i][j] representerar det optimala svaret för delproblemet som sträcker sig över indexen i till j. Den centrala insikten är att vi först löser mindre intervall och sedan bygger upp lösningen för hela intervallet. Mönstret modellerar naturligt problem som matriskedjemultiplikation, palindrompartitionering och ballongexplosion, där delproblemets gränser är det vänstra och högra ändvärdet i ett intervall.
Definition av tillstånd och basfall
För intervall-DP är tillståndet dp[i][j] där i <= j. Basfallen är intervall med ett enda element: dp[i][i]. Dessa löses trivialt — till exempel har en enda matris noll i multiplikationskostnad. Intervall med två element, dp[i][i+1], har ofta också enkla svar. Vi fyller tabellen för ökande intervallängder, från längd 1 upp till 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 intervalsFyllnadsordning: ökande längd
Den kritiska detaljen i intervall-DP är fyllnadsordningen. Vi måste beräkna alla intervall med längden L innan vi beräknar intervall med längden L+1, eftersom ett längre intervall beror på kortare delintervall. Den yttre loopen itererar över intervallängden från 2 till n, den mellersta loopen anger den vänstra gränsen i, och vi beräknar den högra gränsen som 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])Uppställning för matriskedjemultiplikation
Det klassiska intervall-DP-problemet är matriskedjemultiplikation: givet matriser med dimensionerna dims[0..n], hitta det minsta antalet skalära multiplikationer som krävs för att beräkna produkten. Att multiplicera matrisen A(p×q) med B(q×r) kostar p*q*r operationer. dp[i][j] = den minsta kostnaden för att multiplicera matriserna i till j. Delningspunkten k avgör var sekvensen delas upp i två delkedjor.
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])) # 4500Genomgång av DP-tabellen
Vi går igenom matriskedjeexemplet med dimensionerna [10, 30, 5, 60], som representerar tre matriser: A(10×30), B(30×5), C(5×60). För dp[0][2] provar vi delning vid k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, och vid k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Alltså är dp[0][2] = 4500, vilket uppnås genom att multiplicera AB först.
Varför denna fyllnadsordning fungerar
När vi beräknar dp[i][j] använder vi dp[i][k] och dp[k+1][j] för alla k i [i, j-1]. Båda delintervallen har strikt mindre längd än [i, j]. Genom att iterera över längden från liten till stor beräknas alla nödvändiga delintervall innan de behövs. Detta är det grundläggande korrekthetsargumentet för intervall-DP:s fyllnadsordning — kortare intervall är alltid beroenden för längre intervall.
Memoiserad top-down-intervall-DP
Intervall-DP kan alternativt implementeras top-down med memoisering. Vi skriver en rekursiv funktion solve(i, j) som returnerar den optimala kostnaden för intervallet [i, j] och cachar resultaten i en ordlista. Fyllnadsordningen hanteras automatiskt av rekursionen. Top-down är ofta enklare att resonera kring, men kan medföra overhead från funktionsanrop; bottom-up är i praktiken snabbare för stora indata.
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])) # 4500Tids- och minneskomplexitet
Intervall-DP har O(n²) tillstånd (alla par (i, j)), och varje tillstånd itererar över O(n) delningspunkter, vilket ger totalt O(n³) tid. Minnesåtgången är O(n²) för DP-tabellen. För matriskedjemultiplikation med 100 matriser innebär detta 1,000,000 operationer — mycket hanterbart. Mönstret förekommer i många svåra LeetCode-problem och är en favorit i FAANG-intervjuer på grund av sin icke-uppenbara struktur.
Återskapa den optimala lösningen
För att återskapa den faktiska parentesindelningen (inte bara kostnaden) sparar ni en separat tabell split[i][j] som anger vilket k som gav minimum för varje tillstånd. Läs sedan rekursivt av delningarna: reconstruct(i, j) skriver ut den optimala grupperingen genom att rekursivt behandla [i, split[i][j]] och [split[i][j]+1, j]. Denna teknik kan användas för alla intervall-DP-problem.
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], splitMall för alla intervall-DP-problem
Den universella mallen för intervall-DP består av tre delar: (1) initiera basfallen för enskilda element, (2) iterera över ökande längder och för varje längd iterera över giltiga vänstra gränser medan den högra gränsen beräknas, och (3) för varje intervall iterera över alla delningspunkter och tillämpa den problemspecifika rekurrensen. Det enda som ändras mellan problemen är rekurrensformeln i den innersta loopen.
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]Vanliga intervall-DP-problem
Problem som använder intervall-DP är bland annat: matriskedjemultiplikation (minimera antalet operationer), ballongexplosion (maximera antalet mynt), konstig skrivare (minimera antalet utskriftsoperationer), triangulering av polygon med minsta poäng och palindrompartitionering II. Alla använder samma grundstruktur för fyllnadsordningen, men olika rekurrenser. Känn igen mönstret när ett problem frågar efter ett optimalt värde över ett intervall eller en sekvens som kan delas vid valfri inre punkt.
Snabbtest
Testa förståelsen av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen har ni lärt er att intervall-DP använder dp[i][j] för att representera det optimala svaret över ett intervall, att fyllnadsordningen måste följa ökande intervallängd så att delintervall beräknas först och att den universella mallen har O(n³) tid och O(n²) minnesåtgång. Nästa steg är att utforska den längsta palindromiska delsekvensen och delsträngen med hjälp av just detta mönster.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Mönstret för intervall-DP och fyllnadsordning” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Mönstret för intervall-DP och fyllnadsordning”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Mönstret för intervall-DP och fyllnadsordning”?
Definiera DP-tillståndet dp[i][j] för intervall, förklara varför intervall måste fyllas i ordning efter ökande längd och följ mönstret på matrix chain multiplication. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Mönstret för intervall-DP och fyllnadsordning”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Mönstret för intervall-DP och fyllnadsordning
- Längsta palindromiska delsekvens och delsträng
- Palindrome Partitioning II
- Burst Balloons: omvänd intervall-DP