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