Programmation dynamique : l'idée

Si une récursion recalcule les mêmes sous-problèmes, on mémorise leurs résultats : un temps exponentiel devient polynomial.

Deux conditions pour que la DP s'applique : des sous-problèmes qui se chevauchent (les mêmes appels reviennent) et une sous-structure optimale (la solution s'obtient à partir de celles des sous-problèmes).

Les quatre étapes#

1. État : quelles variables décrivent un sous-problème ? (n, (i, j), (i, capacité)…)
2. Transition : comment l'état se calcule à partir d'états plus petits ?
3. Cas de base : les plus petits états, connus directement.
4. Ordre / réponse : dans quel ordre les calculer, et quel état contient la réponse ?

Exemple : Fibonacci, du O(2ⁿ) au O(n)#

fib(n) = fib(n-1) + fib(n-2) recalcule fib(n-2) deux fois, et ainsi de suite en cascade. Avec un cache, chaque valeur n'est calculée qu'une fois.

// Naïf : O(2ⁿ)
function fibSlow(n: number): number {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

// Mémoïsation (top-down) : O(n)
function fib(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

Top-down ou bottom-up ?#

Astuce : écrivez d'abord la récursion naïve correcte, puis ajoutez le cache. Passez en bottom-up seulement si la profondeur ou les performances l'exigent.