Programmation dynamique
Fiche de révision compacte sur la programmation dynamique.
1
Quand l’utiliser
Critères d’application
- Sous-structure optimale.
- États bien définis.
- Transition calculable.
2
État, base, transition
Relation de récurrence
Un état décrit un sous-problème, puis la transition relie cet état à des états plus petits.
Mémoïsation
- 1
Définir l’état.
- 2
Écrire les cas de base.
Mémoisation : à retenir
État, transition, base : si l’un manque, la DP devient floue.
3
Deux écritures
Top-down / Bottom-up
Top-down
- Récursion + cache.
- Calcule à la demande.
- Simple à dériver de la brute.
Bottom-up
- Table + boucle.
- Remplit dans un ordre sûr.
- Souvent plus lisible au coût.
Programmation dynamique tabulée
- 1
Créer la table des états.
- 2
Fixer l’ordre de remplissage.
4
Reconstruction et coût
Reconstruction de solution
Analyse de complexité
| Aspect | Dépend de |
|---|---|
| Temps | Nombre d’états |
| Mémoire | Taille de la table |
| Gain | Répétitions évitées |
5
Exemples classiques
Sac à dos
Objets 1 et 2, valeurs et poids donnés, capacité limitée. On cherche la meilleure valeur totale sans dépasser la capacité.
- Définir l’état par objet courant et capacité restante.
- Tester inclusion ou exclusion de l’objet.
- Conserver le meilleur choix dans la table.
La DP décide pour chaque objet s’il est pris ou non, puis reconstruit l’ensemble optimal.
Plus longue sous-suite
Deux chaînes sont comparées caractère par caractère. On cherche la plus longue sous-suite commune.
- Prendre un état sur deux positions des chaînes.
- Si les caractères sont égaux, avancer dans les deux chaînes.
La DP compare des préfixes, pas des morceaux contigus, et évite les recalculs.
Pièges d’examen
- !!Ne pas confondre sous-suite et sous-chaîne.
- !!Ne pas oublier les indices et les cas de base.
À maîtriser
Résumé
- Le principe d’optimalité guide la récurrence.
- Les sous-problèmes recouvrants justifient la mémorisation.
- La mémoïsation et la table font deux versions d’une même idée.
- La reconstruction prouve la solution finale.