Programmazione dinamica: esempi, problemi comuni e soluzioni

Non c'è dubbio che i problemi di programmazione dinamica possono essere molto intimidatori in un colloquio di programmazione. Anche quando potresti sapere che un problema deve essere risolto utilizzando un metodo di programmazione dinamico, è una sfida riuscire a trovare una soluzione funzionante in un lasso di tempo limitato.

Il modo migliore per essere bravi nei problemi di programmazione dinamica è affrontarne il maggior numero possibile. Sebbene non sia necessario memorizzare la soluzione a ogni problema, è bene avere un'idea di come procedere per implementarne una.

Cos'è la programmazione dinamica?

In poche parole, la programmazione dinamica è un metodo di ottimizzazione per algoritmi ricorsivi, la maggior parte dei quali viene utilizzata per risolvere problemi informatici o matematici.

Puoi anche chiamarla una tecnica algoritmica per risolvere un problema di ottimizzazione suddividendolo in sottoproblemi più semplici. Un principio chiave su cui si basa la programmazione dinamica è che la soluzione ottimale a un problema dipende dalle soluzioni ai suoi sottoproblemi.

Ovunque vediamo una soluzione ricorsiva che ha ripetute chiamate per gli stessi input, possiamo ottimizzarla utilizzando la programmazione dinamica. L'idea è di memorizzare semplicemente i risultati dei sottoproblemi in modo da non doverli ricalcolare quando necessario in seguito.

Le soluzioni programmate dinamicamente hanno una complessità polinomiale che assicura un tempo di esecuzione molto più veloce rispetto ad altre tecniche come la ricorsione o il backtracking. Nella maggior parte dei casi, la programmazione dinamica riduce le complessità temporali, note anche come big-O, da esponenziale a polinomiale.

Cos'è la notazione Big-O?

Il tuo codice deve essere efficiente, ma come fai a dimostrare quanto sia efficiente qualcosa? Con Big-O!

Ora che hai una buona idea di cosa sia la programmazione dinamica, è il momento di esaminare alcuni problemi comuni e le relative soluzioni.

Problemi di programmazione dinamica

1. Problema dello zaino

Dichiarazione problema

Dato un insieme di elementi, ciascuno con un peso e un valore, determinare il numero di ciascun elemento da includere in a raccolta in modo che il peso totale non superi un determinato limite e il valore totale sia grande quanto possibile.

Ti vengono forniti due array di numeri interi valori [0..n-1] e pesi [0..n-1] che rappresentano rispettivamente valori e pesi associati a n elementi. Viene fornito anche un numero intero W che rappresenta la capacità dello zaino.

Qui stiamo risolvendo il problema dello zaino 0/1, il che significa che possiamo scegliere di aggiungere un articolo o di escluderlo.

Algoritmo

• Crea un array bidimensionale con n + 1 righe e w + 1 colonne. Un numero di riga n denota l'insieme di elementi da 1 a ioe un numero di colonna w denota la massima capacità di carico della borsa.
• Il valore numerico in [i] [j] denota il valore totale degli articoli fino a io in una borsa che può trasportare un peso massimo di j.
• Ad ogni coordinata [i] [j] nell'array, scegli il valore massimo che possiamo ottenere senza articolo i, o il valore massimo che possiamo ottenere con articolo iqualunque sia il più grande.
• Il valore massimo ottenibile includendo l'elemento i è la somma dell'elemento io stessa e il valore massimo ottenibile con la capacità residua dello zaino.
• Eseguire questo passaggio finché non si trova il valore massimo per W^th riga.

Codice

def FindMax (W, n, values, weights):
MaxVals = [[0 per x nell'intervallo (W + 1)] per x nell'intervallo (n + 1)]
per i nell'intervallo (n + 1):
per w nell'intervallo (W + 1):
se i == 0 o w == 0:
MaxVals [i] [w] = 0
pesi elif [i-1] <= w:
MaxVals [i] [w] = max (values ​​[i-1]
+ MaxVals [i-1] [w-weights [i-1]], 
MaxVals [i-1] [w])
altro:
MaxVals [i] [w] = MaxVals [i-1] [w]
return MaxVals [n] [W]

2. Problema di cambio moneta

Dichiarazione problema

Supponiamo che ti venga fornito un array di numeri che rappresentano i valori di ciascuna moneta. Dato un importo specifico, trova il numero minimo di monete necessarie per ottenere tale importo.

Algoritmo

• Inizializza un array di dimensioni n + 1, dove n è l'importo. Inizializza il valore di ogni indice io nella matrice per essere uguale all'importo. Questo denota il numero massimo di monete (utilizzando monete di denominazione 1) necessarie per recuperare tale importo.
• Poiché non esiste una denominazione per 0, inizializza il caso base dove matrice [0] = 0.
• Per ogni altro indice io, confrontiamo il valore in esso (che è inizialmente impostato su n + 1) con il valore matrice [i-k] +1, dove K è meno di io. Questo essenzialmente controlla l'intero array fino a i-1 per trovare il numero minimo possibile di monete che possiamo usare.
• Se il valore in qualsiasi matrice [i-k] + 1 è inferiore al valore esistente in matrice [i], sostituire il valore in matrice [i] con quello a matrice [i-k] +1.

Codice

def coin_change (d, amount, k):
numeri = [0] * (importo + 1)
per j nell'intervallo (1, importo + 1):
minimo = importo
per i nell'intervallo (1, k + 1):
se (j> = d [i]):
minimo = min (minimo, 1 + numeri [j-d [i]])
numeri [j] = minimo
numeri di ritorno [importo]

3. Fibonacci

Dichiarazione problema

La serie di Fibonacci è una sequenza di numeri interi in cui il successivo numero intero della serie è la somma dei due precedenti.

È definito dalla seguente relazione ricorsiva: F (0) = 0, F (n) = F (n-1) + F (n-2), dove F (n) è poi^th termine. In questo problema, dobbiamo generare tutti i numeri in una sequenza di Fibonacci fino a un dato n^th termine.

Algoritmo

• Innanzitutto, utilizza un approccio ricorsivo per implementare la relazione di ricorrenza data.
• La risoluzione ricorsiva di questo problema implica la scomposizione F (n) in F (n-1) + F (n-2)e quindi chiamando la funzione con F (n-1) e F (n + 2) come parametri. Lo facciamo fino a quando i casi base dove n = 0, o n = 1 sono raggiunti.
• Ora usiamo una tecnica chiamata memoizzazione. Memorizza i risultati di tutte le chiamate di funzione in una matrice. Ciò garantirà che per ogni n, F (n) deve essere calcolato solo una volta.
• Per qualsiasi calcolo successivo, il suo valore può essere semplicemente recuperato dall'array in tempo costante.

Codice

def fibonacci (n): 
fibNums = [0, 1] 
per i nell'intervallo (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
return fibNums [n] 

4. Successione crescente più lunga

Dichiarazione problema

Trova la lunghezza della sottosequenza crescente più lunga all'interno di un dato array. La sottosequenza crescente più lunga è una sottosequenza all'interno di una matrice di numeri con un ordine crescente. I numeri all'interno della sottosequenza devono essere univoci e in ordine crescente.

Inoltre, gli elementi della sequenza non devono essere consecutivi.

Algoritmo

• Inizia con un approccio ricorsivo in cui calcoli il valore della sottosequenza crescente più lunga di ogni possibile sottoarray dall'indice zero all'indice i, dove i è minore o uguale alla dimensione di Vettore.
• Per trasformare questo metodo in uno dinamico, creare un array per memorizzare il valore per ogni sottosequenza. Inizializza tutti i valori di questo array su 0.
• Ogni indice io di questo array corrisponde alla lunghezza della sottosequenza crescente più lunga per un sottoarray di size io.
• Ora, per ogni chiamata ricorsiva di findLIS (arr, n), controlla il n^th indice dell'array. Se questo valore è 0, calcola il valore utilizzando il metodo nel primo passaggio e memorizzalo in n^th indice.
• Infine, restituisce il valore massimo dall'array. Questa è la lunghezza della sottosequenza crescente più lunga di una data dimensione n.

Codice

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
per i nell'intervallo (1, n):
per j nell'intervallo (0, i):
se myArray [i]> myArray [j] e lis [i] lis [i] = lis [j] +1
maxVal = 0
per i nell'intervallo (n):
maxVal = max (maxVal, lis [i])
return maxVal

Soluzioni a problemi di programmazione dinamica

Ora che hai affrontato alcuni dei problemi di programmazione dinamica più diffusi, è il momento di provare a implementare le soluzioni da solo. Se sei bloccato, puoi sempre tornare indietro e fare riferimento alla sezione sull'algoritmo per ciascun problema sopra.

Considerando quanto siano oggi popolari tecniche come la ricorsione e la programmazione dinamica, non farà male dare un'occhiata ad alcune piattaforme popolari dove puoi imparare tali concetti e affina le tue capacità di programmazione. Anche se potresti non incappare in questi problemi su base giornaliera, li incontrerai sicuramente in un colloquio tecnico.

Naturalmente, avere la conoscenza dei problemi comuni è destinato a pagare i dividendi quando vai per il tuo prossimo colloquio. Quindi apri il tuo IDE preferitoe inizia!

I 9 migliori canali YouTube code-along per imparare la programmazione

Pronto per iniziare a programmare? Questi canali YouTube sono un ottimo modo per iniziare a sviluppare giochi, app, web e altri sviluppi.

Circa l'autore