Exercices corrigés — Programmation dynamique (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Chiffrer le gaspillage
- Le glouton et la dynamique ne rendent pas la même monnaie
- La table du sac, remplie à la main
- Le sens d'une boucle décide du problème résolu
- Somme d'un sous-ensemble, et un mot sur « polynomial »
- La plus longue sous-suite commune : rendre le mot, pas sa longueur
- La distance d'édition en deux lignes
- Ordonnancement de tâches pondérées
- Une mémoïsation qui ne mémoïse rien
- La sous-structure optimale en défaut, sur un exemple de cinq arêtes
- Probleme – De la distance d'édition à la trace des opérations
- Probleme – La plus longue sous-suite croissante, de à
- Probleme – Compter au lieu d'optimiser : combinaisons ou compositions ?
- Probleme – La multiplication chaînée de matrices
- Probleme – Le voyageur de commerce, ou la dynamique sur les sous-ensembles