La Programmation Dynamique

Le principe en une phrase

La programmation dynamique est une technique d'optimisation qui consiste à décomposer un problème en sous-problèmes chevauchants, résoudre chaque sous-problème une seule fois, et stocker le résultat pour le réutiliser. On échange de la mémoire contre du temps.

C'est du bon sens algorithmique : si vous avez déjà calculé quelque chose, ne le recalculez pas. Notez-le et réutilisez-le.

Le problème : les calculs redondants

L'exemple classique est la suite de Fibonacci. Chaque nombre est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13, 21...

L'implémentation récursive naïve :

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Ce code fonctionne, mais il est catastrophiquement lent. Pour calculer fib(5), voici l'arbre d'appels :

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

fib(3) est calculé 2 fois. fib(2) est calculé 3 fois. Pour fib(50), le nombre de calculs redondants explose : la complexité est O(2^n). Concrètement, votre machine mettra plusieurs minutes -- voire ne terminera jamais.

La solution : mémoriser les résultats

L'idée est simple : la première fois qu'on calcule fib(3), on stocke le résultat. La prochaine fois qu'on en a besoin, on le récupère directement.

Approche Top-Down (Mémoïsation)

On garde la structure récursive mais on ajoute un cache :

function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
  // Si déjà calculé, retourner le résultat en cache
  if (memo.has(n)) return memo.get(n)!;
 
  // Cas de base
  if (n <= 1) return n;
 
  // Calculer, stocker, retourner
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
 
console.log(fibMemo(50)); // 12586269025 — instantané

Avec la mémoïsation, chaque valeur est calculée exactement une fois. La complexité passe de O(2^n) à O(n). Pour fib(50), on passe de milliards d'opérations à 50 opérations.

Approche Bottom-Up (Tabulation)

Au lieu de partir du problème global et de descendre récursivement, on part des cas de base et on remonte :

function fibTab(n: number): number {
  if (n <= 1) return n;
 
  const table: number[] = new Array(n + 1);
  table[0] = 0;
  table[1] = 1;
 
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
 
  return table[n];
}

Même complexité O(n), mais sans récursion -- donc pas de risque de stack overflow pour les grandes valeurs. On peut même optimiser l'espace à O(1) en ne gardant que les deux dernières valeurs :

function fibOptimal(n: number): number {
  if (n <= 1) return n;
 
  let prev2 = 0;
  let prev1 = 1;
 
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
 
  return prev1;
}

Les deux conditions de la programmation dynamique

Un problème se prête à la programmation dynamique quand il réunit deux conditions :

1. Sous-problèmes chevauchants (Overlapping Subproblems)

Le même sous-problème apparaît plusieurs fois dans l'arbre de résolution. C'est le cas de Fibonacci : fib(3) est nécessaire à la fois pour fib(4) et fib(5).

2. Sous-structure optimale (Optimal Substructure)

La solution optimale du problème global peut être construite à partir des solutions optimales de ses sous-problèmes. La solution de fib(5) se construit directement à partir de fib(4) et fib(3).

Si seule la première condition est présente, la mémoïsation est utile mais on ne parle pas forcément de programmation dynamique. Si seule la deuxième est présente, un algorithme glouton (greedy) peut suffire.

Exemple concret : le problème du sac à dos

Un cas classique en entretien d'embauche. Vous avez un sac à dos avec une capacité maximale, et des objets avec un poids et une valeur. L'objectif : maximiser la valeur totale sans dépasser la capacité.

interface Item {
  weight: number;
  value: number;
}
 
function knapsack(items: Item[], capacity: number): number {
  const n = items.length;
  // table[i][w] = valeur max avec les i premiers objets et une capacité w
  const table: number[][] = Array.from(
    { length: n + 1 },
    () => new Array(capacity + 1).fill(0)
  );
 
  for (let i = 1; i <= n; i++) {
    const item = items[i - 1];
    for (let w = 0; w <= capacity; w++) {
      // Option 1 : ne pas prendre l'objet i
      table[i][w] = table[i - 1][w];
 
      // Option 2 : prendre l'objet i (si le poids le permet)
      if (item.weight <= w) {
        const valueWithItem = table[i - 1][w - item.weight] + item.value;
        table[i][w] = Math.max(table[i][w], valueWithItem);
      }
    }
  }
 
  return table[n][capacity];
}
 
// Exemple
const items: Item[] = [
  { weight: 2, value: 6 },
  { weight: 3, value: 10 },
  { weight: 4, value: 12 },
  { weight: 5, value: 15 },
];
 
console.log(knapsack(items, 8)); // 22 (objets de poids 3 et 5)

Sans programmation dynamique, il faudrait tester toutes les combinaisons possibles : O(2^n). Avec la tabulation, la complexité tombe à O(n * capacity).

Top-Down vs Bottom-Up : comment choisir ?

En pratique, commencez par la mémoïsation (plus naturelle), puis convertissez en tabulation si les performances ou la profondeur de pile posent problème.

Cas d'usage courants

La programmation dynamique apparaît dans de nombreux problèmes classiques :

• Plus longue sous-séquence commune (LCS) : comparer deux séquences (diff de fichiers, ADN).
• Distance d'édition (Levenshtein) : nombre minimum de modifications pour transformer un mot en un autre. Utilisé dans les correcteurs orthographiques.
• Découpe de barres / pièces de monnaie : trouver la combinaison optimale pour atteindre une valeur cible.
• Chemins dans une grille : compter ou optimiser les chemins possibles dans une matrice.
• Planification d'intervalles pondérés : maximiser la valeur d'activités non chevauchantes.

Résumé

La programmation dynamique repose sur une idée fondamentale : ne jamais faire le même calcul deux fois. En stockant les résultats intermédiaires, on échange un peu de mémoire RAM contre une vitesse d'exécution drastiquement améliorée -- souvent de exponentiel à polynomial.

La prochaine fois que vous écrivez une fonction récursive et que vous suspectez des calculs redondants, dessinez l'arbre d'appels. Si les mêmes noeuds apparaissent plusieurs fois, la mémoïsation est votre alliée.