Un semplice esempio per qualcuno che vuole capire la programmazione dinamica

Question

Sto cercando un esempio gestibile comprensibile per qualcuno che vuole imparare la programmazione dinamica. There are nice answers here about what is dynamic programming. La sequenza fibonacci è un ottimo esempio, ma è troppo piccola per graffiare la superficie. Sembra una materia fantastica da imparare anche se non ho ancora preso la classe degli algoritmi, speriamo che sia sulla mia lista per la primavera.

Answer 1

Calcolare le distanze di Levenshtein è stato uno dei primi problemi risolti con la programmazione dinamica; Penso che sia un buon passo successivo dalla sequenza di Fibonacci in termini di complessità.

http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 2

Dai un'occhiata a questo sito: Dynamic Programming Practice Problems

Answer 3

L'idea alla base di programmazione dinamica è che si sta caching soluzioni (memoizing) a sottoproblemi, anche se penso che c'è di più ad esso che quello.

Ci sono molti problemi di Google Code Jam in modo che le soluzioni richiedano una programmazione dinamica efficiente. Esempi:

Welcome to Code Jam (moderate)

Cheating a Boolean Tree (moderate)

PermRLE (hard)

Nota che ciascuno dei concorsi pratica Code Jam ha una sezione "Analisi Contest" per se siete perplessi cercando di risolvere il problema.

Answer 4

1. Geek per geek ha un ottimo collection di problemi di programmazione dinamica. Sento che questo set è uno dei migliori se ti stai preparando per un colloquio.
2. Se si desiderano piccoli video tutorial su problemi DP, è possibile verificare il problema this impostato dal MIT.

Answer 5

Here is a good tutorial comprendente 29 problemi DP risolti con grande spiegazione.