Un exemple simple pour quelqu'un qui veut comprendre la programmation dynamique

Question

Je cherche un exemple facile à comprendre pour quelqu'un qui veut apprendre la programmation dynamique. Il y a de bonnes réponses ici sur ce qu'est la programmation dynamique. . La séquence de Fibonacci est un excellent exemple, mais elle est trop petite pour effleurer la surface. C'est un sujet intéressant à étudier, même si je n'ai pas encore suivi le cours sur les algorithmes, mais j'espère qu'il sera sur ma liste au printemps.

Answer 1

Consultez ce site : Problèmes pratiques de programmation dynamique

Answer 2

Tutoriel TopCoder pour DP est l'un des meilleurs.

Answer 3

L'idée derrière la programmation dynamique est que vous mettez en cache (mémorisation) les solutions aux sous-problèmes, mais je pense qu'il y a plus que cela.

Il existe de nombreux problèmes de Google Code Jam tels que les solutions nécessitent une programmation dynamique pour être efficaces. Exemples :

Bienvenue à Code Jam (modéré)

Tromper un arbre booléen (modéré)

PermRLE (dur)

Notez que chacun des concours pratiques de Code Jam comporte une section "Analyse du concours" pour le cas où vous auriez des difficultés à résoudre le problème.

Answer 4

Le calcul des distances de Levenshtein est l'un des premiers problèmes que j'ai résolus à l'aide de la programmation dynamique. Je pense qu'il s'agit d'une étape suivante décente de la séquence de Fibonacci en termes de complexité.

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

Answer 5

Vous pouvez également essayer des cours en ligne gratuits sur les algorithmes, comme par exemple https://www.coursera.org/ et choisissez le tutoriel vidéo spécifique sur la programmation dynamique.