Ultimamente sto leggendo la programmazione dinamica. Mi piacerebbe sentire qualcuno che ha iniziato da zero e ora è abbastanza bravo nell'identificare e risolvere i problemi DP. Sto lottando per identificare questi problemi come DP e inquadrare una soluzione concisa.
Ho attraversato la maggior parte dei problemi DP per principianti e risorse MIT ecc.
Vengo da un background di fisica e, quindi, da molta matematica. Trovo facile individuare i problemi adatti alle soluzioni di programmazione ricorsive / dinamiche trovando similitudini con proof by induction .
In prova per induzione hai due parti:
In programmazione ricorsiva / programmazione dinamica:
Quindi, come hanno risposto gli altri, è una questione di esperienza e di raccolta dei suggerimenti, ma puoi riutilizzare altre abilità per guidarti. Dopodiché, devi sempre avere le due parti che ho menzionato: se non lo fai, non funzionerà.
Ad esempio, per generare tutte le permutazioni di un set:
La maggior parte dei problemi di programmazione dinamica può essere risolta tramite la memoizzazione. La Memoizzazione è normalmente più intuitiva e più facile da codificare. Potresti trovare utile pensare in termini di memoizzazione invece di DP.
Di solito è più facile intuire se un problema è adatto alla memoizzazione (i passaggi sono gli stessi di risposta di Slivvz , ma penso che lo spostamento mentale sia un po 'più breve). Tuttavia, una volta risolto un problema tramite la memoizzazione, è possibile esaminare come viene riempita la cache della memo e quindi riordinarla in ordine, senza ricorsione ... che modifica l'algoritmo in un algoritmo di programmazione dinamica.
TL; DR; versione: potresti trovare più semplice comprendere la programmazione dinamica in termini di memorizzazione.
Vedi anche StackOverflow: programmazione dinamica e memoizzazione: approcci bottom-up vs top-down .
La programmazione dinamica è a livello di definizione su due cose:
Sottostruttura ottimale
Soluzioni più grandi possono essere derivate da soluzioni più piccole; risolvere non è bidirezionale.
Sottoprogrammi sovrapposti
Le piccole soluzioni saranno riutilizzate più volte. Se i sottoproblemi non si sovrappongono affatto, allora non si beneficia della DP / memo- ration; quello che hai è divide e conquista invece.
L'approccio generale ai problemi DP è:
Scrivi una versione ricorsiva o iterativa ingenua che funziona.
Si noti che la funzione sta facendo un lavoro ridondante.
Trova un modo per evitare di fare quel lavoro ridondante, spesso tramite meme.
Non ho mai implementato un singolo solutore di programmazione dinamica - il mio background è applicato matematica / fisica / calcolo numerico, non CS - fino a qualche anno fa quando ho iniziato a fare Project Euler problemi. I problemi risolvibili con DP (es. 76 , 158 , 161 , 242 , ma ce ne sono molti altri) si è rivelato il mio genere preferito. Sicuramente stai meglio a individuare quando sarà una tecnica utile: cerca fondamentalmente cose che sembrano essere risolte da una sorta di approccio ricorsivo, dividi e conquisti dove è anche possibile domare l'esplosione di percorsi che necessitano da esplorare riconoscendo sottoproblemi ricorrenti e riutilizzando i risultati precedentemente calcolati; essere in grado di identificare il vettore di stato minimo da memorizzare - e quale "storia" irrilevante può essere cancellata - è il passo cruciale.
Leggi altre domande sui tag algorithms dynamic-programming