ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
La programmation dynamique
La programmation dynamique résout chaque sous-problème une seule fois et mémorise les résultats.
Méthode
- Écrire une relation de récurrence entre le problème et des sous-problèmes.
- Mémoïsation : dictionnaire des résultats (approche descendante).
- Ascendant : tableau rempli du plus petit au plus grand.
Exemples
- Fibonacci : coût proportionnel à n au lieu d’exponentiel.
- Rendu de monnaie : nb(v) = 1 + min nb(v − p) ; coût v × k.
- Distance d’édition : D(i, j) à partir de D(i − 1, j), D(i, j − 1), D(i − 1, j − 1).
Pièges à éviter
- Croire que l’algorithme glouton est toujours optimal.
- Oublier d’initialiser les cas de base du tableau.
- Remplir le tableau dans un ordre où une case utilise une case pas encore calculée.
- Oublier qu’une somme peut être impossible à rendre.