Un exemple simple pour quelqu'un qui veut comprendre la programmation dynamique [fermé]

Je recherche un exemple gérable et compréhensible pour quelqu'un qui veut apprendre la programmation dynamique. Il y a de belles 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 rayer la surface. Cela a l'air d'un excellent sujet à apprendre même si je n'ai pas encore suivi la classe d'algorithmes, j'espère qu'il est sur ma liste pour le printemps.

Consultez ce site: Problèmes de pratique de programmation dynamique

Voici un bon tutoriel comprenant 29 problèmes DP résolus avec une bonne explication.

L'idée derrière la programmation dynamique est que vous mettez en cache (mémorisation) des solutions aux sous-problèmes, même si 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 dans Code Jam (modéré)

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

PermRLE (dur)

Notez que chacun des concours d'entraînement Code Jam a une section "Analyse du concours" si vous êtes perplexe en essayant de résoudre le problème.

1. Geeks for geeks a une grande collection de problèmes de programmation dynamiques. Je pense que cet ensemble est l'un des meilleurs si vous vous préparez pour une entrevue.
2. Si vous voulez de petites vidéos de tutoriel sur les problèmes DP, vous pouvez vérifier cet ensemble de problèmes à partir du MIT.

Le calcul des distances de Levenshtein a été l'un des premiers problèmes que j'ai résolus avec la programmation dynamique; Je pense que c'est une prochaine étape décente de la séquence de Fibonacci en termes de complexité.

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