Accueil › Coding & algorithmique › Mémoïsation et programmation dynamique
Mémoïsation et programmation dynamique
Récursivité, arbres et graphesavance
Quand une récursion recalcule les mêmes sous-problèmes, il suffit de mémoriser.
// Naïf : O(2ⁿ). fib(40) prend plusieurs secondes.
static long fib(int n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
// Mémoïsation (descendant) : O(n)
static long fib(int n, long[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}
// Programmation dynamique (ascendant) : O(n), sans récursion
static long fibPD(int n) {
if (n <= 1) return n;
long[] f = new long[n + 1];
f[1] = 1;
for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
return f[n];
}
// Espace optimisé : O(1)
static long fibO1(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
return a;
}
La démarche en entretien, dans cet ordre :
- Écrire la récursion naïve — elle exprime la relation de récurrence.
- Constater les recalculs, ajouter un cache : c'est la mémoïsation.
- Si l'examinateur pousse : passer en ascendant, puis optimiser l'espace.
Cette progression montre le raisonnement ; arriver directement à la version optimisée le cache.
Les termes à connaître
- Sous-problèmes recouvrants
Le même sous-problème est résolu plusieurs fois par la récursion naïve. C'est la condition qui rend la mémoïsation utile.
- Mémoïsation
Garder le résultat de chaque sous-problème dans un tableau ou une Map, et le réutiliser. Approche descendante : on garde la récursion et on ajoute un cache.
- Programmation dynamique
Remplir un tableau des plus petits sous-problèmes vers les plus grands. Approche ascendante : plus de récursion, donc pas de risque de débordement de pile.
- Relation de récurrence
La formule qui exprime la solution d'un problème à partir de sous-problèmes :
f(n) = f(n-1) + f(n-2). La trouver, c'est résoudre l'exercice.- État
Ce qui identifie un sous-problème : un index, une position, une capacité restante. Le nombre d'états détermine la complexité.
- Optimisation d'espace
Quand
f(n)ne dépend que des deux valeurs précédentes, deux variables suffisent : on passe de O(n) à O(1) en espace.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.