Interval-DP-mønster og udfyldningsrækkefølge
Definér interval-DP-tilstanden dp[i][j], forklar, hvorfor intervaller skal udfyldes i stigende længderækkefølge, og gennemgå mønstret med matrixkædemultiplikation.
Interval-DP-mønster og udfyldningsrækkefølge er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad er interval-DP?
Interval-DP er et mønster inden for dynamisk programmering, hvor tilstanden dp[i][j] repræsenterer det optimale svar på delproblemet, der spænder over indeksene i til j. Den centrale idé er, at vi først løser mindre intervaller og derefter bygger op til hele området. Mønstret modellerer naturligt problemer som multiplikation af matrixkæder, palindromopdeling og ballonsprængning, hvor delproblemets grænser er venstre og højre endepunkt for et område.
Tilstandsdefinition og basistilfælde
I interval-DP er tilstanden dp[i][j], hvor i <= j. Basistilfældene er intervaller med ét element: dp[i][i]. De er trivielle at løse — for eksempel har en enkelt matrix en multiplikationsomkostning på nul. Intervaller med to elementer, dp[i][i+1], har ofte også enkle svar. Vi udfylder tabellen for stigende intervallængder, fra længde 1 til 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 intervalsUdfyldningsrækkefølge: stigende længde
Den afgørende detalje i interval-DP er udfyldningsrækkefølgen. Vi skal beregne alle intervaller med længde L, før vi beregner intervaller med længde L+1, fordi et længere interval afhænger af kortere delintervaller. Den ydre løkke gennemløber intervallængden fra 2 til n, den midterste løkke angiver den venstre grænse i, og vi udleder den højre grænse 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])Opsætning af multiplikation af matrixkæder
Det klassiske interval-DP-problem er multiplikation af matrixkæder: Givet matricer med dimensionerne dims[0..n] skal du finde det mindste antal skalære multiplikationer, der kræves for at beregne produktet. Det koster p*q*r operationer at multiplicere matrix A(p×q) med B(q×r). dp[i][j] = den mindste omkostning ved at multiplicere matricerne fra i til j. Delingspunktet k bestemmer, hvor sekvensen opdeles i to delkæder.
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])) # 4500Gennemgang af DP-tabellen
Lad os gennemgå eksemplet med matrixkæden med dimensionerne [10, 30, 5, 60], som repræsenterer tre matricer: A(10×30), B(30×5), C(5×60). For dp[0][2] prøver vi at dele ved k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, og ved k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Derfor er dp[0][2] = 4500, opnået ved at multiplicere AB først.
Hvorfor denne udfyldningsrækkefølge virker
Når vi beregner dp[i][j], refererer vi til dp[i][k] og dp[k+1][j] for alle k i [i, j-1]. Begge delintervaller har en strengt mindre længde end [i, j]. Ved at gennemløbe længderne fra små til store er alle nødvendige delintervaller beregnet, før vi får brug for dem. Det er det grundlæggende korrekthedsargument for interval-DP's udfyldningsrækkefølge — kortere intervaller er altid afhængigheder for længere intervaller.
Interval-DP oppefra og ned med memoisering
Interval-DP kan også implementeres oppefra og ned med memoisering. Vi skriver en rekursiv funktion solve(i, j), der returnerer den optimale omkostning for intervallet [i, j], og gemmer resultaterne i en ordbog. Rekursionen håndterer automatisk udfyldningsrækkefølgen. Oppefra og ned er ofte lettere at gennemskue, men kan medføre overhead fra funktionskald; nedefra og op er i praksis hurtigere for store input.
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- og pladsforbrug
Interval-DP har O(n²) tilstande (alle par (i, j)), og hver tilstand gennemløber O(n) delingspunkter, hvilket giver O(n³) tidsforbrug i alt. Pladsforbruget er O(n²) til DP-tabellen. Ved multiplikation af en matrixkæde med 100 matricer svarer det til 1.000.000 operationer — det er meget overkommeligt. Mønstret optræder i mange svære LeetCode-problemer og er populært i FAANG-interviews på grund af sin ikke-indlysende struktur.
Genskabelse af den optimale løsning
Hvis du vil genskabe den faktiske parentesering (og ikke kun omkostningen), skal du gemme en separat tabel split[i][j], der registrerer, hvilket k der opnåede minimumsværdien i hver tilstand. Derefter læser du delingerne rekursivt: reconstruct(i, j) udskriver den optimale gruppering ved at kalde sig selv på [i, split[i][j]] og [split[i][j]+1, j]. Denne teknik gælder for alle interval-DP-problemer.
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], splitSkabelon til ethvert interval-DP-problem
Den universelle skabelon til interval-DP består af tre dele: (1) initialisér basistilfældene for enkeltelementer, (2) gennemløb stigende længder, og gennemløb for hver længde de gyldige venstre grænser, mens du beregner den højre grænse, og (3) gennemløb for hvert interval alle delingspunkter, og anvend problemets specifikke rekurrensformel. Det eneste, der ændrer sig fra problem til problem, er rekurrensformlen i den inderste løkke.
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]Almindelige interval-DP-problemer
Problemer, der bruger interval-DP, omfatter: multiplikation af matrixkæder (minimér antallet af operationer), sprængning af balloner (maksimér antallet af mønter), mærkelig printer (minimér antallet af udskrivningsoperationer), minimal pointtriangulering af en polygon og palindromopdeling II. De bruger alle den samme struktur for udfyldningsrækkefølgen, men forskellige rekurrensformler. Genkend mønstret, når et problem beder om en optimal værdi over et område eller en sekvens, der kan opdeles ved et vilkårligt indre punkt.
Hurtigt tjek
Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion har du lært, at interval-DP bruger dp[i][j] til at repræsentere det optimale svar over et område, at udfyldningsrækkefølgen skal følge stigende intervallængde, så delintervallerne beregnes først, og at den universelle skabelon har O(n³) tidsforbrug og O(n²) pladsforbrug. Nu skal vi se på den længste palindromiske delsekvens og delstreng ved hjælp af netop dette mønster.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Interval-DP-mønster og udfyldningsrækkefølge” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Interval-DP-mønster og udfyldningsrækkefølge”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Interval-DP-mønster og udfyldningsrækkefølge”?
Definér interval-DP-tilstanden dp[i][j], forklar, hvorfor intervaller skal udfyldes i stigende længderækkefølge, og gennemgå mønstret med matrixkædemultiplikation. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Interval-DP-mønster og udfyldningsrækkefølge”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Interval-DP-mønster og udfyldningsrækkefølge
- Længste palindromiske delsekvens og delstreng
- Palindrome Partitioning II
- Burst Balloons: Omvendt interval-DP