Programmazione dinamica è un metodo utilizzato in matematica e informatica per risolvere problemi complessi scomponendoli in sottoproblemi più semplici. Risolvendo ciascun sottoproblema una sola volta e memorizzando i risultati, si evitano calcoli ridondanti, portando a soluzioni più efficienti per un'ampia gamma di problemi. Questo articolo fornisce un'esplorazione dettagliata dei concetti di programmazione dinamica, illustrati con esempi.

idea intelligente vs eclissi

Programmazione dinamica

Tabella dei contenuti

• Cos'è la Programmazione Dinamica?
• Come funziona la programmazione dinamica?
• Esempi di programmazione dinamica
• Quando utilizzare la programmazione dinamica?
• Approcci della Programmazione Dinamica
• Algoritmo di programmazione dinamica
• Vantaggi della programmazione dinamica
• Applicazioni della Programmazione Dinamica
• Impara le basi della programmazione dinamica
• Concetti avanzati di programmazione dinamica
• Problemi di programmazione dinamica

Cos'è la Programmazione Dinamica (DP)?

Programmazione dinamica (DP) è un metodo utilizzato in matematica e informatica per risolvere problemi complessi scomponendoli in sottoproblemi più semplici. Risolvendo ciascun sottoproblema una sola volta e memorizzando i risultati, si evitano calcoli ridondanti, portando a soluzioni più efficienti per un'ampia gamma di problemi.

Come funziona la programmazione dinamica (DP)?

• Identificare i sottoproblemi: Dividere il problema principale in sottoproblemi più piccoli e indipendenti.
• Soluzioni per negozi: Risolvi ogni sottoproblema e memorizza la soluzione in una tabella o in un array.
• Costruisci soluzioni: Utilizzare le soluzioni memorizzate per creare la soluzione al problema principale.
• Evitare la ridondanza: Memorizzando le soluzioni, DP garantisce che ogni sottoproblema venga risolto una sola volta, riducendo i tempi di calcolo.

Esempi di Programmazione Dinamica (DP)

Esempio 1: Consideriamo il problema di trovare la sequenza di Fibonacci:

Sequenza di Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Approccio della forza bruta:

Per trovare l'ennesimo numero di Fibonacci utilizzando un approccio di forza bruta, dovresti semplicemente aggiungere il (n-1)esimo E (n-2)esimo Numeri di Fibonacci. Funzionerebbe, ma sarebbe inefficiente per grandi valori di N , poiché richiederebbe il calcolo di tutti i numeri di Fibonacci precedenti.

Approccio alla programmazione dinamica:

Serie di Fibonacci utilizzando la programmazione dinamica

• Sottoproblemi: F(0), F(1), F(2), F(3), …
• Soluzioni per negozi: Creare una tabella per archiviare i valori di F(n) man mano che vengono calcolati.
• Costruisci soluzioni: Per F(n), cerca F(n-1) e F(n-2) nella tabella e sommali.
• Evitare la ridondanza: La tabella garantisce che ogni sottoproblema (ad esempio F(2)) venga risolto solo una volta.

Utilizzando DP, possiamo calcolare in modo efficiente la sequenza di Fibonacci senza dover ricalcolare i sottoproblemi.

dimensione del carattere in lattice

Esempio 2: Sottosequenza comune più lunga (trovare la sottosequenza più lunga comune a due stringhe)

Esempio 3: Percorso più breve in un grafico (trovare il percorso più breve tra due nodi in un grafico)

Esempio 4: Problema dello zaino (trovare il valore massimo degli oggetti che possono essere inseriti in uno zaino con una determinata capacità)

Quando utilizzare la programmazione dinamica (DP)?

La programmazione dinamica è una tecnica di ottimizzazione utilizzata per risolvere problemi che consiste nelle seguenti caratteristiche:

1. Sottostruttura ottimale:

Sottostruttura ottimale significa che combiniamo i risultati ottimali dei sottoproblemi per ottenere il risultato ottimale del problema più grande.

impostazione del percorso Python

Esempio:

Consideriamo il problema di trovare il costo minimo percorso in un grafico ponderato da a fonte nodo ad a destinazione nodo. Possiamo scomporre questo problema in sottoproblemi più piccoli:

• Trovare il minimo costo percorso dal fonte nodo a ciascuno intermedio nodo.
• Trovare il minimo costo percorso da ciascuno intermedio nodo al destinazione nodo.

La soluzione al problema più ampio (trovare il percorso di costo minimo dal nodo sorgente al nodo di destinazione) può essere costruita dalle soluzioni a questi sottoproblemi più piccoli.

2. Sottoproblemi sovrapposti:

Gli stessi sottoproblemi vengono risolti ripetutamente in diverse parti del problema.

Esempio:

Consideriamo il problema del calcolo di Serie di Fibonacci . Per calcolare il numero di Fibonacci all'indice N , dobbiamo calcolare i numeri di Fibonacci negli indici n-1 E n-2 . Ciò significa che il sottoproblema del calcolo del numero di Fibonacci in indice n-1 viene utilizzato due volte nella soluzione al problema più ampio del calcolo del numero di Fibonacci all'indice N .

Approcci della Programmazione Dinamica (DP)

La programmazione dinamica può essere ottenuta utilizzando due approcci:

1. Approccio top-down (memoizzazione):

Nell'approccio top-down, noto anche come memorizzazione , iniziamo con la soluzione finale e la suddividiamo ricorsivamente in sottoproblemi più piccoli. Per evitare calcoli ridondanti, memorizziamo i risultati dei sottoproblemi risolti in una tabella di memorizzazione.

Analizziamo l’approccio top down:

• Inizia con la soluzione finale e la suddivide ricorsivamente in sottoproblemi più piccoli.
• Memorizza le soluzioni ai sottoproblemi in una tabella per evitare calcoli ridondanti.
• Adatto quando il numero di sottoproblemi è elevato e molti di essi vengono riutilizzati.

2. Approccio dal basso verso l'alto (tabulazione):

Nell'approccio dal basso verso l'alto, noto anche come tabulazione , iniziamo con i sottoproblemi più piccoli e gradualmente arriviamo alla soluzione finale. Memorizziamo i risultati dei sottoproblemi risolti in una tabella per evitare calcoli ridondanti.

Analizziamo l’approccio bottom-up:

• Inizia con i sottoproblemi più piccoli e arriva gradualmente alla soluzione finale.
• Riempie una tabella con soluzioni ai sottoproblemi in modo bottom-up.
• Adatto quando il numero di sottoproblemi è piccolo e la soluzione ottima può essere calcolata direttamente dalle soluzioni di sottoproblemi più piccoli.

Programmazione dinamica (DP) Algoritmo

La programmazione dinamica è una tecnica algoritmica che risolve problemi complessi suddividendoli in sottoproblemi più piccoli e memorizzando le loro soluzioni per un uso futuro. È particolarmente efficace per i problemi che contiene sottoproblemi sovrapposti E sottostruttura ottimale.

Algoritmi comuni che utilizzano la programmazione dinamica:

• Sottosequenza comune più lunga (LCS): Trova la sottosequenza comune più lunga tra due stringhe.
• Percorso più breve in un grafico: Trova il percorso più breve tra due nodi in un grafico.
• Problema dello zaino: Determina il valore massimo degli oggetti che possono essere inseriti in uno zaino con una determinata capacità.
• Moltiplicazione della catena di matrici: Ottimizza l'ordine di moltiplicazione della matrice per ridurre al minimo il numero di operazioni.
• Sequenza di Fibonacci: Calcola l'ennesimo numero di Fibonacci.

Vantaggi della programmazione dinamica (DP)

La programmazione dinamica presenta una vasta gamma di vantaggi, tra cui:

• Evita di ricalcolare gli stessi sottoproblemi più volte, con conseguente notevole risparmio di tempo.
• Garantisce che venga trovata la soluzione ottimale considerando tutte le possibili combinazioni.
• Suddivide i problemi complessi in sottoproblemi più piccoli e più gestibili.

Applicazioni della Programmazione Dinamica (DP)

La programmazione dinamica ha una vasta gamma di applicazioni, tra cui:

• Ottimizzazione: Problema dello zaino, problema del percorso minimo, problema del massimo sottoarray
• Informatica: Sottosequenza comune più lunga, distanza di modifica, corrispondenza delle stringhe
• Ricerche operative: Gestione dell'inventario, programmazione, allocazione delle risorse

Ora esploriamo una tabella di marcia completa per padroneggiare la programmazione dinamica.

cm in piedi e pollici

Impara le basi della programmazione dinamica (DP)

• Cos'è la memorizzazione? Un tutorial completo
• Tabulazione vs memorizzazione
• Proprietà ottimale della sottostruttura
• Proprietà dei sottoproblemi sovrapposti
• Come risolvere un problema di programmazione dinamica?

• Numeri di Fibonacci
• ennesimo numero catalano
• Numeri campanello (numero di modi per suddividere un set)
• Coefficiente binomiale
• Problema cambio moneta
• Problema della somma dei sottoinsiemi
• Calcola nCr % p
• Tagliare un'asta
• Algoritmo di recinzione di pittura
• Sottosequenza comune più lunga
• Sottosequenza crescente più lunga
• Sottosequenza più lunga tale che la differenza tra adiacenti sia una
• Sottomatrice quadrata di dimensione massima con tutti 1
• Percorso costo minimo
• Numero minimo di salti per raggiungere la fine
• Sottostringa comune più lunga (soluzione DP ottimizzata per lo spazio)
• Contare i modi per raggiungere l'ennesima scala utilizzando il passaggio 1, 2 o 3
• Conta tutti i percorsi possibili da in alto a sinistra a in basso a destra di una matrice mXn
• Percorsi unici in una griglia con ostacoli

2. Problemi medi sulla Programmazione Dinamica (DP)

• Algoritmo di Floyd Warshall
• Algoritmo di Bellman-Ford
• 0-1 Problema con lo zaino
• Stampa di oggetti nello zaino 0/1
• Zaino illimitato (ripetizione di articoli consentita)
• Puzzle di caduta delle uova
• Problema di interruzione delle parole
• Problema di copertura del vertice
• Problema di impilamento delle piastrelle
• Problema di impilamento delle scatole
• Problema di partizione
• Problema del commesso viaggiatore | Set 1 (programmazione ingenua e dinamica)
• Sottosequenza palindromica più lunga
• Sottosequenza crescente comune più lunga (LCS + LIS)
• Trova tutte le somme di sottoinsiemi (o sottosequenze) distinte di un array
• Pianificazione ponderata del lavoro
• Count Derangements (permutazione tale che nessun elemento appare nella sua posizione originale)
• Inserzioni minime per formare un palindromo
• Corrispondenza del modello di caratteri jolly
• Modi per disporre le palline in modo tale che le palline adiacenti siano di tipo diverso

3. Problemi difficili sulla programmazione dinamica (DP)

• Partizionamento palindromo
• Problema del ritorno a capo automatico delle parole
• Il problema della partizione del pittore
• Programma per il problema del ponte e della torcia
• Moltiplicazione di catene di matrici
• Stampa delle parentesi nel problema della moltiplicazione della catena di matrici
• Rettangolo di somma massima in una matrice 2D
• Profitto massimo acquistando e vendendo un'azione al massimo k volte
• Costo minimo per ordinare le stringhe utilizzando operazioni di storno con costi diversi
• Conteggio delle sottosequenze AP (progressione aritmetica) in un array
• Introduzione alla Programmazione Dinamica sugli Alberi
• Altezza massima dell'albero quando qualsiasi nodo può essere considerato come radice
• Sottostringa ripetuta e non sovrapposta più lunga

Link veloci:

• Impara la struttura dei dati e gli algoritmi | Tutorial DSA
• Le 20 principali domande per l'intervista sulla programmazione dinamica
• 'Problemi pratici' sulla programmazione dinamica
• ‘Quiz’ sulla Programmazione Dinamica