Intervall-DP-mønster og utfyllingsrekkefølge

Intervall-DP er et mønster for dynamisk programmering der tilstanden dp[i][j] representerer det optimale svaret for delproblemet som dekker indeksene i til og med j. Den viktigste innsikten er at vi først løser mindre intervaller og bygger oss opp til hele området. Dette mønsteret modellerer naturlig problemer som matrisekjedemultiplikasjon, palindrompartisjonering og ballongsprekking, der grensene for delproblemet er venstre og høyre endepunkt i et område.

For intervall-DP er tilstanden dp[i][j], der i <= j. Basistilfellene er intervaller med ett element: dp[i][i]. Disse er trivielt løst – for eksempel har én matrise en multiplikasjonskostnad på null. Intervaller med to elementer, dp[i][i+1], har ofte også enkle svar. Vi fyller ut tabellen for økende intervallengder, fra lengde 1 til og med n.

Den avgjørende detaljen i intervall-DP er fyllingsrekkefølgen. Vi må beregne alle intervaller med lengde L før vi beregner intervaller med lengde L+1, fordi et lengre intervall avhenger av kortere delintervaller. Den ytre løkken går gjennom intervallengdene fra 2 til n, den midterste løkken setter venstre grense i, og vi utleder høyre grense som j = i + L - 1.

Det klassiske intervall-DP-problemet er matrisekjedemultiplikasjon: Gitt matriser med dimensjoner dims[0..n] skal du finne det minste antallet skalære multiplikasjoner som trengs for å beregne produktet. Det koster p*q*r operasjoner å multiplisere matrise A(p×q) med B(q×r). dp[i][j] = den minste kostnaden for å multiplisere matrise i til og med j. Delingspunktet k avgjør hvor sekvensen deles i to delkjeder.

La oss gå gjennom matrisekjedeeksempelet med dimensjonene [10, 30, 5, 60], som representerer tre matriser: A(10×30), B(30×5), C(5×60). For dp[0][2] prøver vi deling 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. Dermed er dp[0][2] = 4500, oppnådd ved å multiplisere AB først.

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 delintervallene har strengt mindre lengde enn [i, j]. Ved å gå gjennom lengdene fra små til store er alle nødvendige delintervaller beregnet før vi trenger dem. Dette er det grunnleggende korrekthetsargumentet for fyllingsrekkefølgen i intervall-DP – kortere intervaller er alltid avhengigheter for lengre intervaller.

Intervall-DP kan også implementeres top-down med memoisering. Vi skriver en rekursiv funksjon solve(i, j) som returnerer den optimale kostnaden for intervallet [i, j], og mellomlagrer resultatene i en ordbok. Rekursjonen håndterer fyllingsrekkefølgen automatisk. Top-down er ofte enklere å resonnere over, men kan ha ekstra kostnad for funksjonskall; bottom-up er raskere i praksis for store inndata.

Intervall-DP har O(n²) tilstander (alle par (i, j)), og hver tilstand går gjennom O(n) delingspunkter, noe som gir O(n³) tid totalt. Plassforbruket er O(n²) for DP-tabellen. For matrisekjedemultiplikasjon med 100 matriser tilsvarer dette 1 000 000 operasjoner – svært overkommelig. Mønsteret dukker opp i mange vanskelige LeetCode-problemer og er populært i FAANG-intervjuer på grunn av den lite åpenbare strukturen.

For å gjenopprette den faktiske parenteseringen (ikke bare kostnaden) lagrer du en separat split[i][j]-tabell som registrerer hvilken k som oppnådde minimumet for hver tilstand. Les deretter delingene rekursivt: reconstruct(i, j) skriver ut den optimale grupperingen ved å rekursere på [i, split[i][j]] og [split[i][j]+1, j]. Denne teknikken gjelder for alle intervall-DP-problemer.

Den universelle malen for intervall-DP har tre deler: (1) initialiser basistilfellene for enkeltelementer, (2) gå gjennom økende lengder og, for hver lengde, gå gjennom gyldige venstregrenser mens du beregner høyregrensen, og (3) gå gjennom alle delingspunkter for hvert intervall og bruk den problemspesifikke rekurrensen. Det eneste som endres mellom problemene, er rekurrensformelen i den innerste løkken.

Problemer som bruker intervall-DP, inkluderer: Matrix Chain Multiplication (minimer antall operasjoner), Burst Balloons (maksimer antall mynter), Strange Printer (minimer antall utskriftsoperasjoner), Minimum Score Triangulation of Polygon og Palindrome Partitioning II. Alle bruker det samme skjelettet for fyllingsrekkefølgen, men ulike rekurrenser. Gjenkjenn mønsteret når et problem ber om en optimal verdi over et område eller en sekvens som kan deles ved et vilkårlig indre punkt.

I denne leksjonen lærte du at intervall-DP bruker dp[i][j] til å representere det optimale svaret over et område, at fyllingsrekkefølgen må følge økende intervallengde slik at delintervaller beregnes først, og at den universelle malen har O(n³) tid og O(n²) plass. Neste gang utforsker vi den lengste palindromiske delsekvensen og delstrengen ved hjelp av nettopp dette mønsteret.