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. Anche se non devi necessariamente 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 la complessità temporale, nota anche come big-O , da esponenziale a polinomiale.

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

Problemi di programmazione dinamica

1. Problema dello zaino

Dichiarazione problema

Dato un insieme di articoli, ciascuno con un peso e un valore, determinare il numero di ogni articolo da includere in una collezione in modo che il peso totale non superi un determinato limite e il valore totale sia il più grande possibile.

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

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

Algoritmo

• Crea una matrice bidimensionale con n + 1 righe e w + 1 colonne. Un numero di riga n denota l’insieme di articoli da 1 a i , e un numero di colonna w denota la capacità di carico massima della borsa.
• Il valore numerico in [i] [j] denota il valore totale degli articoli fino a i in una borsa che può trasportare un peso massimo di j.
• Ad ogni coordinata [i] [j] dell’array, scegli il valore massimo che possiamo ottenere senza l’ elemento i , o il valore massimo che possiamo ottenere con l’ elemento i — qualunque sia il più grande.
• Il valore massimo ottenibile includendo l’articolo i è la somma dell’articolo i stesso e il valore massimo ottenibile con la capacità residua dello zaino.
• Eseguire questo passaggio fino a trovare il valore massimo per il W ^° fila.

Codice

def FindMax(W, n, values, weights):
 MaxVals = [[0 for x in range(W + 1)] for x in range(n + 1)]
 for i in range(n + 1):
 for w in range(W + 1):
 if i == 0 or w == 0:
 MaxVals[i][w] = 0
 elif weights[i-1] <= w:
 MaxVals[i][w] = max(values[i-1]
 + MaxVals[i-1][w-weights[i-1]],
 MaxVals[i-1][w])
 else:
 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 dimensione n + 1 , dove n è l’importo. Inizializza il valore di ogni indice i nell’array in modo che sia 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 in cui array [0] = 0 .
• Per ogni altro indice i , confrontiamo il valore in esso (che è inizialmente impostato su n + 1 ) con l’ array di valori [ik] +1 , dove k è minore di i . 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 [ik] + 1 è minore del valore esistente in matrice [i] , sostituire il valore in matrice [i] con quello in matrice [ik] +1 .

Codice

def coin_change(d, amount, k):
 numbers = [0]*(amount+1)
 for j in range(1, amount+1):
 minimum = amount
 for i in range(1, k+1):
 if(j >= d[i]):
 minimum = min(minimum, 1 + numbers[jd[i]])
 numbers[j] = minimum
 return numbers[amount]

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) è l’ ^ennesimo termine. In questo problema, dobbiamo generare tutti i numeri in una sequenza di Fibonacci fino a un dato n- ^esimo termine.

Algoritmo

• In primo luogo, utilizzare un approccio ricorsivo per implementare la relazione di ricorrenza data.
• La risoluzione ricorsiva di questo problema comporta la scomposizione di F (n) in F (n-1) + F (n-2) , e quindi la chiamata alla funzione con F (n-1) e F (n + 2) come parametri. Lo facciamo fino a quando non vengono raggiunti i casi base in cui n = 0 o n = 1 .
• 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) debba 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]
 for i in range(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 dell’array.
• 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 i di questo array corrisponde alla lunghezza della sottosequenza crescente più lunga per un sottoarray di dimensione i .
• Ora, per ogni chiamata ricorsiva di findLIS (arr, n) , controlla l’ n- ^esimo indice dell’array. Se questo valore è 0, quindi calcolare il valore utilizzando il metodo nel primo passaggio e riporlo al n ^° indice.
• Infine, restituisci 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
 for i in range (1 , n):
 for j in range(0 , i):
 if myArray[i] > myArray[j] and lis[i]< lis[j] + 1 :
 lis[i] = lis[j]+1
 maxVal= 0
 for i in range(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ù popolari, è 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 apprendere tali concetti e affinare le tue abilità di programmazione . Anche se potresti non incorrere in questi problemi su base giornaliera, li incontrerai sicuramente in un colloquio tecnico.

Naturalmente, avere il know-how di problemi comuni è destinato a pagare i dividendi quando vai per il tuo prossimo colloquio. Quindi apri il tuo IDE preferito e inizia!