Formations — 1 037 leçons en français

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 :

  1. Écrire la récursion naïve — elle exprime la relation de récurrence.
  2. Constater les recalculs, ajouter un cache : c'est la mémoïsation.
  3. 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.

Lire l'explication détaillée et faire le quiz →

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.