Demistificazione della programmazione dinamica

Come costruire e codificare algoritmi di programmazione dinamica

Forse ne hai sentito parlare durante la preparazione per le interviste di programmazione. Forse hai lottato attraverso questo in un corso di algoritmi. Forse stai cercando di imparare a programmare da solo e ti è stato detto da qualche parte lungo il cammino che è importante capire la programmazione dinamica. L'uso della programmazione dinamica (DP) per scrivere algoritmi è tanto essenziale quanto temuto.

E chi può incolpare chi si allontana da esso? La programmazione dinamica sembra intimidatoria perché mal insegnata. Molti tutorial si concentrano sul risultato - spiegando l'algoritmo, anziché sul processo - trovare l'algoritmo. Questo incoraggia la memorizzazione, non la comprensione.

Durante la mia lezione sugli algoritmi quest'anno, ho messo insieme il mio processo per risolvere i problemi che richiedono una programmazione dinamica. Alcune parti provengono dal mio professore di algoritmi (a cui è dovuto molto credito!) E parti dalla mia dissezione di algoritmi di programmazione dinamica.

Ma prima di condividere il mio processo, iniziamo con le basi. Che cos'è la programmazione dinamica, comunque?

Programmazione dinamica definita

La programmazione dinamica equivale a scomporre un problema di ottimizzazione in sotto-problemi più semplici e memorizzare la soluzione per ciascun sotto-problema in modo che ogni sotto-problema sia risolto una sola volta.

Ad essere onesti, questa definizione potrebbe non avere un senso totale fino a quando non vedrai un esempio di sotto-problema. Va bene, verrà nella prossima sezione.

Ciò che spero di comunicare è che DP è una tecnica utile per i problemi di ottimizzazione, quei problemi che cercano la soluzione massima o minima dati determinati vincoli, perché esamina tutti i possibili sotto-problemi e non ricalcola mai la soluzione per nessun sotto-problema. Ciò garantisce la correttezza e l'efficienza, che non possiamo dire della maggior parte delle tecniche utilizzate per risolvere o approssimare algoritmi. Questo da solo rende DP speciale.

Nelle prossime due sezioni, spiegherò cos'è un sotto-problema, e quindi motiverò perché l'archiviazione di soluzioni - una tecnica nota come memoization - è importante nella programmazione dinamica.

Sotto-problemi su Sotto-problemi su Sotto-problemi

I problemi secondari sono versioni più piccole del problema originale. In effetti, i problemi secondari spesso sembrano una versione riformulata del problema originale. Se formulati correttamente, i problemi secondari si basano l'uno sull'altro per ottenere la soluzione al problema originale.

Per darti un'idea migliore di come funziona, troviamo il sotto-problema in un esempio di problema di programmazione dinamica.

Fingi di essere tornato negli anni '50 a lavorare su un computer IBM-650. Sai cosa significa: schede perforate! Il tuo lavoro è per un uomo o una donna, l'IBM-650 per un giorno. Ti viene dato un numero naturale n di schede perforate da eseguire. Ogni punchcard i deve essere eseguita ad un'ora di inizio predeterminata s_i e interrompere l'esecuzione ad un'ora di fine predeterminata f_i. È possibile eseguire una sola scheda perforata contemporaneamente su IBM-650. Ogni scheda perforata ha anche un valore associato v_i basato su quanto sia importante per la tua azienda.

Problema: in qualità di responsabile dell'IBM-650, è necessario determinare la pianificazione ottimale delle schede perforate che massimizza il valore totale di tutte le schede perforate eseguite.

Poiché esaminerò questo esempio in modo dettagliato in questo articolo, per ora ti prenderò in giro con il suo sotto-problema:

Problema secondario: la pianificazione del valore massimo per le schede perforate da i a n tale che le schede perforate siano ordinate in base all'ora di inizio.

Notare come il problema secondario suddivide il problema originale in componenti che compongono la soluzione. Con il problema secondario, è possibile trovare la pianificazione del valore massimo per le schede perforate da n-1 a n, quindi per le schede perforate da n-2 a n e così via. Trovando le soluzioni per ogni singolo sotto-problema, è quindi possibile affrontare il problema originale stesso: la pianificazione del valore massimo per le schede perforate da 1 a n. Poiché il problema secondario si presenta come il problema originale, è possibile utilizzare i problemi secondari per risolvere il problema originale.

Nella programmazione dinamica, dopo aver risolto ogni sotto-problema, è necessario memorizzarlo o memorizzarlo. Scopriamo perché nella sezione seguente.

Motivare la memorizzazione con i numeri di Fibonacci

Quando ti viene detto di implementare un algoritmo che calcola il valore di Fibonacci per un dato numero, cosa faresti? La maggior parte delle persone che conosco opterebbe per un algoritmo ricorsivo che assomiglia a questo in Python:

def fibonacciVal (n):
  se n == 0:
    ritorna 0
  elif n == 1:
    ritorno 1
  altro:
    ritorno fibonacciVal (n-1) + fibonacciVal (n-2)

Questo algoritmo raggiunge il suo scopo, ma a un costo enorme. Ad esempio, diamo un'occhiata a cosa deve calcolare questo algoritmo per risolvere n = 5 (abbreviato come F (5)):

F (5)
                    / \
                   / \
                  / \
               F (4) F (3)
            / \ / \
          F (3) F (2) F (2) F (1)
         / \ / \ / \
       F (2) F (1) F (1) F (0) F (1) F (0)
       / \
     F (1) F (0)

L'albero sopra rappresenta ogni calcolo che deve essere fatto per trovare il valore di Fibonacci per n = 5. Nota come il sotto-problema per n = 2 viene risolto tre volte. Per un esempio relativamente piccolo (n = 5), è un sacco di calcolo ripetuto e sprecato!

Che cosa succede se, invece di calcolare il valore di Fibonacci per n = 2 tre volte, creiamo un algoritmo che lo calcola una volta, memorizza il suo valore e accede al valore di Fibonacci memorizzato per ogni successiva occorrenza di n = 2? Questo è esattamente ciò che fa la memorizzazione.

Con questo in mente, ho scritto una soluzione di programmazione dinamica al problema del valore di Fibonacci:

def fibonacciVal (n):
  memo = [0] * (n + 1)
  memo [0], memo [1] = 0, 1
  per i nell'intervallo (2, n + 1):
    memo [i] = memo [i-1] + memo [i-2]
  ritorno memo [n]

Si noti come la soluzione del valore restituito provenga dall'array di memoization memo [], che viene ripetutamente compilato dal ciclo for. Con "iterativamente" intendo che il memo [2] viene calcolato e memorizzato prima del memo [3], memo [4], ... e memo [n]. Poiché memo [] è compilato in questo ordine, la soluzione per ciascun sotto-problema (n = 3) può essere risolta dalle soluzioni ai suoi precedenti sotto-problemi (n = 2 e n = 1) perché questi valori erano già memorizzati in memo [] in un momento precedente.

Memoizzazione non significa ricalcolo, il che rende un algoritmo più efficiente. Pertanto, la memoizzazione garantisce l'efficienza della programmazione dinamica, ma sta scegliendo il giusto sotto-problema che garantisce che un programma dinamico passi attraverso tutte le possibilità al fine di trovare il migliore.

Ora che abbiamo affrontato la memoizzazione e i problemi secondari, è tempo di imparare il processo di programmazione dinamica. Fibbia.

Il mio processo di programmazione dinamica

Passaggio 1: identificare il sotto-problema in parole.

Troppo spesso, i programmatori si dedicheranno alla scrittura del codice prima di pensare criticamente al problema in questione. Non bene. Una strategia per accendere il cervello prima di toccare la tastiera è usare parole, inglese o altro, per descrivere il sotto-problema che hai identificato all'interno del problema originale.

Se stai risolvendo un problema che richiede una programmazione dinamica, prendi un pezzo di carta e pensa alle informazioni necessarie per risolvere questo problema. Scrivi il sotto-problema tenendo presente questo.

Ad esempio, nel problema delle schede perforate, ho affermato che il problema secondario può essere scritto come "la pianificazione del valore massimo per le schede perforate da i a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio". Ho scoperto questo problema secondario realizzando che, al fine di determinare la pianificazione del valore massimo per le schede perforate da 1 a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio, dovrei trovare la risposta ai seguenti sotto-problemi:

  • La pianificazione del valore massimo per le schede perforate da n-1 a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio
  • La pianificazione del valore massimo per le schede perforate da n-2 a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio
  • La pianificazione del valore massimo per le schede perforate da n-3 a n tale che le schede perforate siano ordinate in base all'ora di inizio
  • (Et cetera)
  • La pianificazione del valore massimo per le schede perforate da 2 a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio

Se riesci a identificare un sotto-problema che si basa su precedenti sotto-problemi per risolvere il problema in questione, allora sei sulla strada giusta.

Passaggio 2: scrivere il sotto-problema come una decisione matematica ricorrente.

Dopo aver identificato a parole un sotto-problema, è tempo di scriverlo matematicamente. Perché? Bene, la ricorrenza matematica, o decisione ripetuta, che trovi alla fine sarà quella che metterai nel tuo codice. Inoltre, scrivere il sotto-problema controlla matematicamente il tuo sotto-problema in parole dal passaggio 1. Se è difficile codificare il tuo sotto-problema dal passaggio 1 in matematica, allora potrebbe essere il sotto-problema sbagliato!

Ci sono due domande che mi pongo ogni volta che provo a trovare una ricorrenza:

  • Quale decisione prendo ad ogni passo?
  • Se il mio algoritmo si trova al passaggio i, quali informazioni avrebbe bisogno per decidere cosa fare al passaggio i + 1? (E a volte: se il mio algoritmo è al passaggio i, quali informazioni sono necessarie per decidere cosa fare nel passaggio i-1?)

Torniamo al problema del punchcard e poniamo queste domande.

Quale decisione prendo ad ogni passo? Supponiamo che le schede perforate siano ordinate in base all'ora di inizio, come indicato in precedenza. Per ogni scheda perforata finora compatibile con la pianificazione (l'ora di inizio è successiva all'ora di fine della scheda perforata attualmente in esecuzione), l'algoritmo deve scegliere tra due opzioni: eseguire o non eseguire la scheda perforata.

Questo programma dinamico sceglie tra due opzioni per ogni passaggio, proprio come il nostro caro amico Amleto!

Se il mio algoritmo si trova al passaggio i, quali informazioni avrebbe bisogno per decidere cosa fare al passaggio i + 1? Per decidere tra le due opzioni, l'algoritmo deve conoscere la prossima scheda perforata compatibile nell'ordine. La successiva punchcard compatibile per una determinata punchcard p è la punchcard q tale che s_q (l'ora di inizio predeterminata per la punchcard q) si verifica dopo f_p (il tempo di fine predeterminato per la punchcard p) e la differenza tra s_q e f_p è ridotta al minimo. Abbandonando il discorso matematico, la prossima scheda perforata compatibile è quella con il primo orario di inizio dopo che la scheda perforata corrente termina l'esecuzione.

Se il mio algoritmo è al passaggio i, quali informazioni sono necessarie per decidere cosa fare nel passaggio i-1? L'algoritmo deve conoscere le decisioni future: quelle prese per le schede perforate da i a n per decidere di eseguire o meno le schede perforate i-1.

Ora che abbiamo risposto a queste domande, forse hai iniziato a formare una decisione matematica ricorrente nella tua mente. Altrimenti, va bene lo stesso, diventa più facile scrivere ricorrenze quando ti esponi a problemi di programmazione più dinamici.

Senza ulteriori indugi, ecco la nostra ricorrenza:

OPT (i) = max (v_i + OPT (next [i]), OPT (i + 1))

Questa ricorrenza matematica richiede alcune spiegazioni, soprattutto per coloro che non ne hanno mai scritto uno prima. Uso OPT (i) per rappresentare la pianificazione del valore massimo per schede perforate da i a n in modo tale che le schede perforate siano ordinate in base all'ora di inizio. Sembra familiare, vero? OPT (•) è il nostro sotto-problema dal passaggio 1.

Al fine di determinare il valore di OPT (i), consideriamo due opzioni e vogliamo prendere il massimo di queste opzioni al fine di raggiungere il nostro obiettivo: la pianificazione del valore massimo per tutte le schede perforate. Una volta scelta l'opzione che fornisce il massimo risultato al punto i, memorizziamo il suo valore come OPT (i).

Le due opzioni - per eseguire o non eseguire punchcard i - sono rappresentate matematicamente come segue:

v_i + OPT (successivo [i])

Questa clausola rappresenta la decisione di eseguire punchcard i. Aggiunge il valore guadagnato dall'esecuzione della punchcard i a OPT (next [i]), dove next [i] rappresenta la successiva punchcard compatibile successiva alla punchcard i. OPT (successivo [i]) fornisce la pianificazione del valore massimo per i biglietti da visita successivi [i] attraverso n in modo tale che i biglietti da visita siano ordinati in base all'ora di inizio. L'aggiunta di questi due valori insieme produce una pianificazione del valore massimo per le schede perforate da i a n in modo tale che le schede perforate vengano ordinate in base all'ora di inizio se viene eseguita la scheda perforata i.

OPT (i + 1)

Al contrario, questa clausola rappresenta la decisione di non eseguire punchcard i. Se la punchcard i non viene eseguita, il suo valore non viene acquisito. OPT (i + 1) fornisce la pianificazione del valore massimo per le schede perforate da i + 1 a n in modo tale che le schede perforate vengano ordinate in base all'ora di inizio. Pertanto, OPT (i + 1) fornisce la pianificazione del valore massimo per schede perforate da i a n in modo tale che le schede perforate vengano ordinate in base all'ora di inizio se la scheda perforata i non viene eseguita.

In questo modo, la decisione presa in ciascuna fase dei problemi con le schede perforate viene codificata matematicamente per riflettere il sotto-problema nella Fase 1.

Passaggio 3: risolvere il problema originale utilizzando i passaggi 1 e 2.

Nel passaggio 1, abbiamo scritto il sotto-problema per il problema della punchcard in parole. Nel passaggio 2, abbiamo scritto una decisione matematica ricorrente che corrisponde a questi sotto-problemi. Come possiamo risolvere il problema originale con queste informazioni?

OPT (1)

È così semplice. Poiché il sotto-problema riscontrato nel passaggio 1 è la pianificazione del valore massimo per le schede perforate da n in modo tale che le schede perforate siano ordinate in base all'ora di inizio, possiamo scrivere la soluzione al problema originale come pianificazione del valore massimo per le schede perforate da 1 a n in modo tale che le schede perforate siano ordinate per ora di inizio. Poiché i passaggi 1 e 2 vanno di pari passo, il problema originale può anche essere scritto come OPT (1).

Passaggio 4: determinare le dimensioni dell'array di memoization e la direzione in cui deve essere riempito.

Hai trovato il passaggio 3 ingannevolmente semplice? Sembra proprio così. Potresti pensare, come può OPT (1) essere la soluzione al nostro programma dinamico se si basa su OPT (2), OPT (prossimo [1]) e così via?

Hai ragione a notare che OPT (1) si affida alla soluzione di OPT (2). Ciò segue direttamente dal passaggio 2:

OPT (1) = max (v_1 + OPT (successivo [1]), OPT (2))

Ma questo non è un problema schiacciante. Ripensare all'esempio di memoization di Fibonacci. Per trovare il valore di Fibonacci per n = 5, l'algoritmo si basa sul fatto che i valori di Fibonacci per n = 4, n = 3, n = 2, n = 1 e n = 0 erano già memorizzati. Se compiliamo la nostra tabella di memoization nell'ordine corretto, la dipendenza di OPT (1) su altri sotto-problemi non è un grosso problema.

Come possiamo identificare la direzione corretta per riempire la tabella di memoization? Nel problema delle schede perforate, poiché sappiamo che OPT (1) si basa sulle soluzioni di OPT (2) e OPT (successivo [1]), e che le schede perforate 2 e successive [1] hanno orari di inizio dopo la scheda perforata 1 a causa dell'ordinamento, abbiamo possiamo dedurre che dobbiamo riempire la nostra tabella di memoization da OPT (n) a OPT (1).

Come determiniamo le dimensioni di questo array di memoization? Ecco un trucco: le dimensioni dell'array sono uguali al numero e alla dimensione delle variabili su cui si basa OPT (•). Nel problema della scheda perforata, abbiamo OPT (i), il che significa che OPT (•) si basa solo sulla variabile i, che rappresenta il numero della scheda perforata. Ciò suggerisce che il nostro array di memoization sarà monodimensionale e che le sue dimensioni saranno n poiché ci sono n schede perforate totali.

Se sappiamo che n = 5, il nostro array di memoization potrebbe apparire così:

memo = [OPT (1), OPT (2), OPT (3), OPT (4), OPT (5)]

Tuttavia, poiché molti linguaggi di programmazione iniziano a indicizzare le matrici su 0, potrebbe essere più conveniente creare questo array di memoization in modo che i suoi indici si allineino con i numeri delle schede perforate:

memo = [0, OPT (1), OPT (2), OPT (3), OPT (4), OPT (5)]

Passaggio 5: codificalo!

Per codificare il nostro programma dinamico, abbiamo messo insieme i passaggi 2–4. L'unica nuova informazione di cui hai bisogno per scrivere un programma dinamico è un caso di base, che puoi trovare mentre armeggi con il tuo algoritmo.

Un programma dinamico per il problema del punchcard avrà un aspetto simile al seguente:

def punchcardSchedule (n, valori, successivo):
 # Inizializza array di memoization - Passaggio 4
  memo = [0] * (n + 1)
  
 # Imposta la base
  memo [n] = valori [n]
  
 # Crea tabella di memoization da n a 1 - Passaggio 2
  per i nell'intervallo (n-1, 0, -1):
    memo [i] = max (v_i + memo [next [i]], memo [i + 1])
 
 # Riporta la soluzione al problema originale OPT (1) - Passaggio 3
  memo di ritorno [1]

Complimenti per aver scritto il tuo primo programma dinamico! Ora che ti sei bagnato i piedi, ti guiderò attraverso un diverso tipo di programma dinamico.

Paradosso della scelta: opzioni multiple DP Esempio

Non correlato a DP, ma una rappresentazione accurata di quanto possano essere strazianti le decisioni multi-opzione.

Sebbene il precedente esempio di programmazione dinamica avesse una decisione a due opzioni - eseguire o non eseguire una scheda perforata - alcuni problemi richiedono che vengano prese in considerazione più opzioni prima di poter prendere una decisione in ogni fase.

Tempo per un nuovo esempio.

Fai finta di vendere i bracciali dell'amicizia a n clienti e il valore di quel prodotto aumenta monotonicamente. Ciò significa che il prodotto ha prezzi {p_1, ..., p_n} tali che p_i ≤ p_j se il cliente j viene dopo il cliente i. Questi n clienti hanno valori {v_1, ..., v_n}. Un determinato cliente comprerò un braccialetto di amicizia al prezzo p_i se e solo se p_i ≤ v_i; altrimenti le entrate ottenute da quel cliente sono 0. Supponiamo che i prezzi siano numeri naturali.

Problema: devi trovare la serie di prezzi che ti assicurano il massimo reddito possibile dalla vendita dei tuoi braccialetti di amicizia.

Dedica un secondo a pensare a come potresti risolvere questo problema prima di esaminare le mie soluzioni ai passaggi 1 e 2.

Passaggio 1: identificare il sotto-problema in parole.

Sotto-problema: le entrate massime ottenute dai clienti i attraverso n in modo tale che il prezzo per il cliente i-1 fosse fissato a q.

Ho riscontrato questo sotto-problema rendendomi conto che per determinare le entrate massime per i clienti da 1 a n, avrei dovuto trovare la risposta ai seguenti sotto-problemi:

  • Le entrate massime ottenute dai clienti da n-1 a n in modo tale che il prezzo per il cliente n-2 fosse fissato a q.
  • Le entrate massime ottenute dai clienti da n-2 a n in modo tale che il prezzo per il cliente n-3 fosse fissato a q.
  • (Et cetera)

Si noti che ho introdotto una seconda variabile q nel sotto-problema. L'ho fatto perché, al fine di risolvere ogni sotto-problema, ho bisogno di sapere il prezzo che ho impostato per il cliente prima di quel sotto-problema. La variabile q garantisce la natura monotonica dell'insieme dei prezzi e la variabile i tiene traccia del cliente corrente.

Passaggio 2: scrivere il sotto-problema come una decisione matematica ricorrente.

Ci sono due domande che mi pongo ogni volta che provo a trovare una ricorrenza:

  • Quale decisione prendo ad ogni passo?
  • Se il mio algoritmo si trova al passaggio i, quali informazioni avrebbe bisogno per decidere cosa fare al passaggio i + 1? (E a volte: se il mio algoritmo è al punto i, quali informazioni dovrebbero decidere cosa fare nel punto i-1?)

Ritorniamo al problema del braccialetto dell'amicizia e facciamo queste domande.

Quale decisione prendo ad ogni passo? Decido a quale prezzo vendere il mio braccialetto di amicizia al cliente attuale. Poiché i prezzi devono essere numeri naturali, so che dovrei impostare il mio prezzo per il cliente i nell'intervallo da q - il prezzo impostato per il cliente i-1 - a v_i - il prezzo massimo al quale comprerò un braccialetto di amicizia.

Se il mio algoritmo si trova al passaggio i, quali informazioni avrebbe bisogno per decidere cosa fare al passaggio i + 1? Il mio algoritmo deve conoscere il prezzo impostato per il cliente i e il valore del cliente i + 1 per decidere a quale numero naturale impostare il prezzo per il cliente i + 1.

Con questa conoscenza, posso scrivere matematicamente la ricorrenza:

OPT (i, q) = max ~ ([Entrate (v_i, a) + OPT (i + 1, a)])
tale che max ~ trova il massimo sopra a nell'intervallo q ≤ a ≤ v_i

Ancora una volta, questa ricorrenza matematica richiede alcune spiegazioni. Poiché il prezzo per il cliente i-1 è q, per il cliente i, il prezzo a rimane intero q oppure cambia in un numero intero compreso tra q + 1 e v_i. Per trovare le entrate totali, aggiungiamo le entrate dal cliente i alle entrate massime ottenute dai clienti da + 1 a n in modo tale che il prezzo per il cliente i sia stato fissato a.

In altre parole, per massimizzare le entrate totali, l'algoritmo deve trovare il prezzo ottimale per il cliente i controllando tutti i prezzi possibili tra q e v_i. Se v_i ≤ q, il prezzo a deve rimanere a q.

E gli altri passaggi?

Lavorare attraverso i passaggi 1 e 2 è la parte più difficile della programmazione dinamica. Come esercizio, ti suggerisco di seguire i passaggi 3, 4 e 5 da solo per verificare la tua comprensione.

Analisi di runtime di programmi dinamici

Ora per la parte divertente della scrittura di algoritmi: analisi di runtime. Userò la notazione big-O durante questa discussione. Se non hai ancora familiarità con big-O, ti suggerisco di leggerlo qui.

Generalmente, il runtime di un programma dinamico è composto dalle seguenti funzioni:

  • Pre-processing
  • Quante volte viene eseguito il ciclo for
  • Quanto tempo impiega la ricorrenza a eseguirsi in uno per l'iterazione ciclica
  • Post produzione

Nel complesso, il runtime assume la forma seguente:

Pre-elaborazione + Loop * Ricorrenza + Post-elaborazione

Eseguiamo un'analisi di runtime del problema della scheda perforata per familiarizzare con big-O per programmi dinamici. Ecco il programma dinamico problema punchcard:

def punchcardSchedule (n, valori, successivo):
 # Inizializza array di memoization - Passaggio 4
  memo = [0] * (n + 1)
  
 # Imposta la base
  memo [n] = valori [n]
  
 # Crea tabella di memoization da n a 1 - Passaggio 2
  per i nell'intervallo (n-1, 0, -1):
    memo [i] = max (v_i + memo [next [i]], memo [i + 1])
 
 # Riporta la soluzione al problema originale OPT (1) - Passaggio 3
  memo di ritorno [1]

Analizziamo il suo tempo di esecuzione:

  • Pre-elaborazione: qui, questo significa costruire l'array di memoization. Sopra).
  • Quante volte viene eseguito il ciclo for: O (n).
  • Quanto tempo impiega la ricorrenza a eseguirsi in una per l'iterazione del ciclo: la ricorrenza richiede un tempo costante per l'esecuzione perché prende una decisione tra due opzioni in ciascuna iterazione. O (1).
  • Post-elaborazione: nessuna qui! O (1).

L'autonomia complessiva del programma dinamico del problema della scheda perforata è O (n) O (n) * O (1) + O (1) o, in forma semplificata, O (n).

Ce l'hai fatta!

Bene, tutto qui: sei ancora un passo avanti per diventare un mago della programmazione dinamica!

Margaret Hamilton: uno dei tanti maghi di programmazione nella nostra storia!

Un'ultima saggezza: continua a praticare la programmazione dinamica. Indipendentemente da quanto possano sembrare frustranti questi algoritmi, scrivere ripetutamente programmi dinamici renderà i problemi secondari e le ricorrenze più naturali. Ecco un elenco di crowdsourcing di classici problemi di programmazione dinamica da provare.

Quindi esci e partecipa alle tue interviste, lezioni e vita (ovviamente) con le tue nuove conoscenze di programmazione dinamica!

Mille grazie a Steven Bennett, Claire Durand e Prithaj Nath per aver revisionato questo post. Grazie al professor Hartline per avermi così entusiasta della programmazione dinamica che ne ho scritto a lungo.

Ti piace quello che leggi? Diffondi l'amore piacendo e condividendo questo pezzo. Hai pensieri o domande? Contattami su Twitter o nei commenti qui sotto.