Dynamic Programming
La programmation dynamique décompose un problème en sous-problèmes chevauchants et stocke leurs solutions pour éviter les recalculs, en résolvant de bas en haut ou de haut en bas (mémoïsation).
Objectif
Résoudre efficacement les problèmes d'optimisation possédant une sous-structure optimale et des sous-problèmes chevauchants.
Mécanisme
Identifier la sous-structure optimale : la solution optimale contient des solutions optimales de sous-problèmes. Bas en haut : remplir la table par taille croissante. Haut en bas : récursion avec mémoïsation. Classiques : sac à dos, plus longue sous-séquence commune, distance d'édition, multiplication chaînée de matrices.
Cas d’usage
- Conception d'algorithmes
- Problèmes d'optimisation
- Analyse de séquences