Stavo leggendo su Programmazione dinamica e sono abbastanza nuovo ad esso. Volevo sapere se la programmazione dinamica può essere applicata in modo "iterativo" e "ricorsivo" o è buona pratica applicarla solo in uno dei modi. Qualsiasi buon esempio/link sarebbe utile.Programmazione dinamica ricorsiva o iterativa
Sì, DP può essere applicato a entrambi.
Inizia da qui: http://en.wikipedia.org/wiki/Dynamic_programming
Allora avete Dynamic Programming: From novice to advanced e A Tutorial on Dynamic Programming
Per la prima esercitazione, troverete i link ai TopCoder.com problemi per la pratica (ciascuno di questi problemi hanno anche un Editorial che spiega l'idea dietro la soluzione.
programmazione dinamica può essere visto (in molti casi) come soluzione ricorsiva implementata in retromarcia.
N ormalmente, in una ricorsione, si calcolerebbe x(n+1) = f(x(n)) con alcune condizioni di stop per n=0 (o qualche altro valore).
In molti casi la funzione f è una funzione min/max, ma non deve essere. Inoltre, la funzione non deve prendere una singola variabile.
programmazione dinamica possa risolvere questo problema calcolando f(0), quindi f(1), quindi f(2) ecc
Con più di una variabile, ci sarebbe normalmente essere qualche ordine naturale per calcolare la funzione.
Un esempio che la programmazione dinamica può risolvere: Ti vengono dati 3 mazze da golf. Ogni golf club può inviare una pallina da golf x unità di distanza in avanti (ad esempio, 24, 37 e 54 unità). La domanda è: puoi colpire un buco che è esattamente a 200 unità di distanza? E se puoi, qual è il numero minimo di colpi che ti servono.
La soluzione ricorsiva sarebbe qualcosa di simile:
shots(200) = min(shots(200-24),shots(200-37),shots(200-54))
Questo permetterebbe un'implementazione banale, in cui la funzione shot(n) restituisce 0 se n è 0, un numero enorme se n è minore di 0, e l'espressione sopra altrimenti.
Tuttavia, per valori elevati di n si raggiungono gli stessi valori ripetutamente, da diversi rami dell'espressione sopra. In tal caso, è meglio partire da 0 e calcolare shots(0), shots(1), shots(2) ecc. Questa sarebbe la soluzione di "programmazione dinamica" a questo problema - utilizzando il tempo lineare e lo spazio costante invece del tempo esponenziale (attraversando un albero a 3 vie) e lo spazio lineare al meglio (per lo stack di chiamate).
L'approccio top-down è ancora considerato programmazione dinamica se si inserisce la memoizzazione. DP bottom-up e DP top-down sono entrambi DP. – harold
@harold hai ragione, probabilmente avrei dovuto aggiungere qualcosa sulla memoizzazione (è un po 'più difficile da usare se si desidera mantenere i requisiti di memoria ragionevoli, è necessario sapere quando è possibile "dimenticare" i valori mentre con bottom-up è abbastanza chiaro). –
Mentre la soluzione ricorsiva con il caching guarda solo un piccolo sottoinsieme dei numeri 0..200, la soluzione iterativa dovrebbe esaminarli tutti (almeno non è semplice evitarlo). Quindi, sembra che la soluzione ricorsiva possa funzionare più velocemente in questo caso. – AlwaysLearning