Découvrir la programmation dynamique : sous-problèmes, mémoïsation et optimalité
Repérer, sur un problème d'optimisation ou de dénombrement, des sous-problèmes qui se chevauchent, et expliquer pourquoi mémoriser leurs résultats évite de les recalculer.

Les points essentiels
- La programmation dynamique résout un problème en le décomposant en sous-problèmes plus petits, dont les solutions se combinent pour obtenir celle du problème initial.
- Elle devient utile quand les sous-problèmes se chevauchent : un même sous-problème est demandé plusieurs fois par la récursion naïve, qui le recalcule à chaque fois.
Les mots à connaître
- Sous-problème
- Version plus petite ou plus simple du problème, définie par un jeu de paramètres, dont le résultat sert à construire la solution du problème de départ (par exemple fib(k) avec k<n).
- Mémoïsation
- Technique qui enregistre le résultat d'un appel de fonction associé à ses arguments, afin de le renvoyer directement si les mêmes arguments se représentent, sans refaire le calcul.
Un exemple pour comprendre
Soit la fonction fib définie par fib(0)=0, fib(1)=1 et fib(n)=fib(n-1)+fib(n-2). (a) Dessiner les appels de la version récursive naïve pour n=5 et repérer les sous-problèmes répétés. (b) Écrire la version mémoïsée et donner le nombre d'additions pour n=5.
(a) fib(5) appelle fib(4) et fib(3). fib(4) appelle fib(3) et fib(2) ; fib(3) appelle fib(2) et fib(1), etc. fib(3) est calculé 2 fois, fib(2) 3 fois, fib(1) 5 fois. Au total, la version naïve effectue 15 appels pour n=5 alors que seules les valeurs fib(0) à fib(5) sont distinctes. (b) Version mémoïsée : def fib(n, memo={}): if n in memo: return memo[n]; if n<2: return n; memo[n]=fib(n-1,memo)... en pratique on passe un dictionnaire créé à l'appel externe : def fib(n, memo=None): if memo is None: memo={}; if n<2: return n; if n not in memo: memo[n]=fib(n-1,memo)+fib(n-2,memo); return memo[n]. Chaque valeur de fib(2) à fib(5) n'est calculée qu'une fois : 4 additions (fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5). On passe de 15 appels à 4 additions, et le rapport s'accentue très vite avec n.

