Schema della DP sugli intervalli e ordine di riempimento
Definisca lo stato della DP sugli intervalli dp[i][j], spieghi perché gli intervalli devono essere riempiti in ordine di lunghezza crescente e segua lo schema sul problema della moltiplicazione a catena di matrici.
Schema della DP sugli intervalli e ordine di riempimento è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Che cos'è la DP sugli intervalli?
La DP sugli intervalli è uno schema di programmazione dinamica in cui lo stato dp[i][j] rappresenta la soluzione ottimale del sottoproblema che copre gli indici da i a j. L'idea fondamentale è risolvere prima gli intervalli più piccoli e costruire progressivamente la soluzione per l'intero intervallo. Questo schema si adatta naturalmente a problemi come la moltiplicazione a catena di matrici, il partizionamento palindromico e lo scoppio dei palloncini, in cui i limiti del sottoproblema sono gli estremi sinistro e destro di un intervallo.
Definizione dello stato e casi base
Nella DP sugli intervalli, lo stato è dp[i][j] dove i <= j. I casi base sono gli intervalli composti da un singolo elemento: dp[i][i]. Sono risolti banalmente: per esempio, una singola matrice ha costo di moltiplicazione pari a zero. Anche gli intervalli di due elementi, dp[i][i+1], hanno spesso risposte semplici. Si riempie la tabella per lunghezze di intervallo crescenti, partendo dalla lunghezza 1 fino a 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 intervalsOrdine di riempimento: lunghezza crescente
Il dettaglio fondamentale nella DP sugli intervalli è l'ordine di riempimento. È necessario calcolare tutti gli intervalli di lunghezza L prima di calcolare quelli di lunghezza L+1, perché un intervallo più lungo dipende da sottintervalli più brevi. Il ciclo esterno scorre la lunghezza dell'intervallo da 2 a n, il ciclo intermedio imposta il limite sinistro i e il limite destro si ricava come 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])Configurazione della moltiplicazione a catena di matrici
Il classico problema di DP sugli intervalli è la moltiplicazione a catena di matrici: date matrici con dimensioni dims[0..n], si deve trovare il numero minimo di moltiplicazioni scalari necessarie per calcolare il prodotto. Moltiplicare la matrice A(p×q) per B(q×r) costa p*q*r operazioni. dp[i][j] = costo minimo per moltiplicare le matrici da i a j. Il punto di separazione k stabilisce dove dividere la sequenza in due sottocatene.
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])) # 4500Analisi della tabella DP
Analizziamo l'esempio della catena di matrici con dimensioni [10, 30, 5, 60], che rappresenta tre matrici: A(10×30), B(30×5), C(5×60). Per dp[0][2] proviamo la separazione in k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, e in k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Quindi dp[0][2] = 4500, ottenuto moltiplicando prima AB.
Perché questo ordine di riempimento funziona
Quando si calcola dp[i][j], si fa riferimento a dp[i][k] e dp[k+1][j] per ogni k in [i, j-1]. Entrambi i sottintervalli hanno una lunghezza strettamente inferiore a quella di [i, j]. Scorrendo le lunghezze dalla più piccola alla più grande, tutti i sottintervalli necessari vengono calcolati prima di essere utilizzati. Questo è l'argomento fondamentale per dimostrare la correttezza dell'ordine di riempimento nella DP sugli intervalli: gli intervalli più brevi sono sempre dipendenze di quelli più lunghi.
DP sugli intervalli top-down con memoizzazione
In alternativa, la DP sugli intervalli può essere implementata in modalità top-down con memoizzazione. Si scrive una funzione ricorsiva solve(i, j) che restituisce il costo ottimale per l'intervallo [i, j] e si memorizzano i risultati in un dizionario. L'ordine di riempimento viene gestito automaticamente dalla ricorsione. L'approccio top-down è spesso più facile da comprendere, ma può comportare un overhead dovuto alle chiamate di funzione; quello bottom-up è più veloce in pratica per input di grandi dimensioni.
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])) # 4500Complessità temporale e spaziale
La DP sugli intervalli ha O(n²) stati (tutte le coppie (i, j)) e ogni stato scorre O(n) punti di separazione, per un totale di O(n³) in tempo. Lo spazio occupato è O(n²) per la tabella DP. Per la moltiplicazione a catena di 100 matrici, si tratta di 1.000.000 di operazioni: un numero facilmente gestibile. Questo schema compare in molti problemi difficili di LeetCode ed è molto apprezzato nei colloqui FAANG per la sua struttura non intuitiva.
Ricostruzione della soluzione ottimale
Per ricostruire la parentesizzazione effettiva (non solo il costo), memorizzi una tabella separata split[i][j] che registri quale k ha prodotto il minimo in ogni stato. Poi legga ricorsivamente le separazioni: reconstruct(i, j) stampa il raggruppamento ottimale ricorrendo su [i, split[i][j]] e [split[i][j]+1, j]. Questa tecnica si applica a tutti i problemi di DP sugli intervalli.
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], splitSchema per qualsiasi problema di DP sugli intervalli
Lo schema universale della DP sugli intervalli ha tre parti: (1) inizializzare i casi base per gli elementi singoli, (2) scorrere le lunghezze crescenti e, per ogni lunghezza, scorrere i limiti sinistri validi calcolando il limite destro e (3) per ogni intervallo, iterare su tutti i punti di separazione e applicare la ricorrenza specifica del problema. L'unico elemento che cambia da un problema all'altro è la formula della ricorrenza nel ciclo più interno.
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]Problemi comuni di DP sugli intervalli
I problemi che utilizzano la DP sugli intervalli includono: Moltiplicazione a catena di matrici (minimizzare le operazioni), Scoppio dei palloncini (massimizzare le monete), Stampante strana (minimizzare le operazioni di stampa), Triangolazione del poligono con punteggio minimo e Partizionamento palindromico II. Tutti usano la stessa struttura di base per l'ordine di riempimento, ma ricorrenze diverse. Riconosca questo schema quando un problema chiede un valore ottimale su un intervallo o una sequenza che può essere divisa in qualsiasi punto interno.
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: la DP sugli intervalli usa dp[i][j] per rappresentare la soluzione ottimale su un intervallo, l'ordine di riempimento deve seguire lunghezze crescenti, così i sottintervalli vengono calcolati per primi e lo schema universale richiede O(n³) di tempo e O(n²) di spazio. Ora analizzeremo la sottosequenza e la sottostringa palindromiche più lunghe usando proprio questo schema.
Domande Frequenti
La lezione «Schema della DP sugli intervalli e ordine di riempimento» è gratuita?
Sì — il testo completo di «Schema della DP sugli intervalli e ordine di riempimento» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Schema della DP sugli intervalli e ordine di riempimento»?
Definisca lo stato della DP sugli intervalli dp[i][j], spieghi perché gli intervalli devono essere riempiti in ordine di lunghezza crescente e segua lo schema sul problema della moltiplicazione a cat… Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Schema della DP sugli intervalli e ordine di riempimento»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema della DP sugli intervalli e ordine di riempimento
- Sottosequenza e sottostringa palindroma più lunga
- Partizionamento palindromico II
- Burst Balloons: DP sugli intervalli al contrario