La programmation dynamique

Les problèmes algorithmiques les plus redoutables sont des problèmes d'optimisation : on cherche une solution qui maximise ou minimise une fonction. Le voyageur de commerce en est l'archétype — trouver la tournée de coût minimal visitant toutes les villes. Deux stratégies s'opposent alors. Les algorithmes gloutons (greedy) prennent la meilleure décision locale à chaque étape : ils sont rapides mais ne garantissent presque jamais l'optimum global. La recherche exhaustive essaie toutes les possibilités et retient la meilleure : elle est correcte, mais son coût en temps est généralement prohibitif.

La programmation dynamique (dynamic programming) marie le meilleur des deux mondes. Elle explore systématiquement toutes les possibilités — donc elle est correcte — tout en stockant les résultats déjà calculés pour ne jamais recalculer deux fois la même chose — donc elle est efficace. Skiena la décrit comme « probablement la technique la plus facile à appliquer une fois qu'on l'a comprise » ; ses algorithmes sont souvent plus rapides à réinventer qu'à retrouver dans un livre. Mais tant qu'on n'a pas saisi le truc, cela ressemble à de la magie.

L'idée centrale : mémoire contre calcul

La programmation dynamique est essentiellement un compromis espace-temps (space-time tradeoff). Recalculer une même quantité est sans gravité tant que cela ne pèse pas sur les performances. Quand le poids des recalculs devient un fardeau, on a intérêt à stocker le résultat du premier calcul et à le consulter ensuite plutôt qu'à le refaire.

L'approche se construit toujours à partir d'un algorithme récursif correct. On ne s'inquiète de l'accélérer qu'une fois la récursivité validée. Le truc consiste à repérer si l'algorithme récursif naïf calcule encore et encore les mêmes sous-problèmes. Si oui, ranger chaque réponse dans une table pour la relire au lieu de la recalculer débouche sur un algorithme efficace.

Fibonacci : trois programmes, trois mondes

Le compromis se voit le mieux sur une récurrence simple, les nombres de Fibonacci, définis par F(n) = F(n-1) + F(n-2) avec F(0) = 0 et F(1) = 1.

Récursif naïf : exponentiel

La traduction directe de la définition est élégante mais catastrophique.

// O(1.6^n) : temps EXPONENTIEL. Inutilisable au-delà de ~45.
function fibNaif(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibNaif(n - 1) + fibNaif(n - 2);
}

Pourquoi est-ce si lent ? L'arbre de récursion recalcule sans fin. Pour F(6), F(4) est calculé des deux côtés de l'arbre et F(2) pas moins de cinq fois. Comme F(n+1)/F(n) tend vers le nombre d'or φ ≈ 1.618, l'arbre possède au moins 1.6^n feuilles. Sur la machine de Skiena, ce programme mettait plus de 7 minutes à calculer les 45 premiers nombres de Fibonacci.

Mémoïsation (top-down) : cacher les résultats

La parade évidente : stocker (ou cacher) chaque F(k) dans une table indexée par k, et vérifier la table avant de calculer.

// O(n) temps, O(n) espace. La récursion est inchangée,
// seul le cache « regarde avant de traverser la rue ».
function fibMemo(n: number, cache: number[] = []): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (cache[n] !== undefined) return cache[n]; // déjà connu ?
  cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  return cache[n];
}

Cette version s'exécute instantanément. Le nouvel arbre de récursion n'a plus de branchement significatif : seuls les appels du côté gauche calculent, ceux de droite trouvent leur réponse dans le cache et reviennent aussitôt. La fonction est appelée exactement deux fois pour chaque valeur entre 0 et n, d'où un temps linéaire O(n).

Attention : cacher n'a de sens que si l'espace des paramètres distincts est modeste. Stocker les résultats serait inutile pour le tri rapide, le retour sur trace ou le parcours en profondeur, car leurs appels récursifs ont tous des paramètres distincts. On ne stocke pas ce qu'on ne reverra jamais.

Tabulation (bottom-up) : remplir une table

On peut faire encore mieux en spécifiant explicitement l'ordre d'évaluation et en supprimant toute récursion. On évalue du plus petit au plus grand, en remplissant un tableau.

// O(n) temps, O(n) espace, sans aucun appel récursif.
function fibTab(n: number): number {
  const f = [0, 1];
  for (let i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
  return f[n];
}

// O(n) temps, O(1) espace : la récurrence ne dépend que
// des deux dernières valeurs, inutile de tout garder.
function fibUltime(n: number): number {
  if (n === 0) return 0;
  let avant2 = 0;
  let avant1 = 1;
  for (let i = 2; i <= n; i++) {
    const suivant = avant1 + avant2;
    avant2 = avant1;
    avant1 = suivant;
  }
  return avant1;
}

Le tableau récapitule ce voyage du naïf au tabulé optimisé.

Approche	Direction	Temps	Espace
Récursif naïf	top-down	O(1.6ⁿ)	O(n) (pile)
Mémoïsation	top-down	O(n)	O(n)
Tabulation	bottom-up	O(n)	O(n)
Tabulation optimisée	bottom-up	O(n)	O(1)

Coefficients binomiaux

Même leçon pour les coefficients binomiaux. La formule n!/((n-k)!·k!) provoque facilement des dépassements arithmétiques intermédiaires, même quand le résultat final tient dans un entier. La récurrence du triangle de Pascal est bien plus stable : chaque nombre est la somme des deux qui le surplombent, C(n,k) = C(n-1,k-1) + C(n-1,k), avec C(n,0) = 1 et C(k,k) = 1. On remplit une table dans un ordre tel que les deux valeurs nécessaires sont toujours déjà calculées.

Trouver la récurrence : le cœur de l'art

Skiena résume la méthode en trois étapes :

1. Formuler la réponse comme une récurrence ou un algorithme récursif.
2. Montrer que le nombre de valeurs distinctes des paramètres est borné par un polynôme (espoir : petit).
3. Spécifier un ordre d'évaluation garantissant que les résultats partiels nécessaires sont toujours disponibles au moment voulu.

La mécanique des tables est secondaire ; tout l'art réside dans la formulation de la bonne récurrence.

La distance d'édition

Comment chercher la sous-chaîne la plus proche d'un motif, malgré des fautes de frappe ? « Thou shalt not kill » devient « You should not murder » au fil des siècles. Pour le mesurer, on définit une distance d'édition (edit distance, ou distance de Levenshtein) : le nombre minimal de transformations pour passer d'une chaîne à l'autre. Trois opérations naturelles, chacune de coût 1 :

• Substitution — remplacer un caractère par un autre (« shot » → « spot »).
• Insertion — ajouter un caractère (« ago » → « agog »).
• Suppression — retirer un caractère (« hour » → « our »).

Penser à l'envers

L'idée décisive : raisonner sur le dernier caractère. Soit on l'a apparié ou substitué, soit inséré, soit supprimé. Chopper ce dernier caractère laisse une paire de chaînes plus courtes. Si l'on connaissait le coût d'édition de ces sous-paires, on choisirait la meilleure option. Définissons D[i][j] comme le coût minimal pour transformer le préfixe P[1..i] en T[1..j]. C'est le minimum de trois extensions :

D[i][j] = min(
  D[i-1][j-1] + (Pᵢ == Tⱼ ? 0 : 1),   # appariement ou substitution
  D[i-1][j]   + 1,                     # suppression dans P
  D[i][j-1]   + 1                      # insertion dans P
)

La version récursive pure est correcte mais impossiblement lente : elle branche trois fois à chaque position, soit au moins 3^n. Or il n'existe que |P|·|T| paires (i, j) distinctes. En les rangeant dans une table 2D, on les calcule une seule fois.

Implémentation tabulée avec reconstruction

On consacre la ligne 0 et la colonne 0 aux conditions aux bords : transformer une chaîne de longueur i en chaîne vide coûte i (autant d'insertions ou de suppressions). On enregistre dans une seconde table le parent de chaque cellule — l'opération qui y a mené — pour reconstruire l'alignement.

type Op = "MATCH" | "INSERT" | "DELETE";

// O(n·m) temps et espace. Renvoie coût + opérations.
function distanceEdition(p: string, t: string): {
  cout: number;
  operations: Op[];
} {
  const n = p.length;
  const m = t.length;
  const D: number[][] = [];
  const par: (Op | null)[][] = [];
  for (let i = 0; i <= n; i++) {
    D[i] = new Array(m + 1).fill(0);
    par[i] = new Array(m + 1).fill(null);
  }
  for (let i = 1; i <= n; i++) { D[i][0] = i; par[i][0] = "DELETE"; }
  for (let j = 1; j <= m; j++) { D[0][j] = j; par[0][j] = "INSERT"; }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      const sub = D[i - 1][j - 1] + (p[i - 1] === t[j - 1] ? 0 : 1);
      const del = D[i - 1][j] + 1; // caractère en trop dans p
      const ins = D[i][j - 1] + 1; // caractère en trop dans t
      D[i][j] = sub;
      par[i][j] = "MATCH";
      if (del < D[i][j]) { D[i][j] = del; par[i][j] = "DELETE"; }
      if (ins < D[i][j]) { D[i][j] = ins; par[i][j] = "INSERT"; }
    }
  }
  return { cout: D[n][m], operations: reconstruire(par, n, m) };
}

// Backtrack : on remonte les pointeurs parent jusqu'à (0,0).
function reconstruire(
  par: (Op | null)[][], i: number, j: number,
): Op[] {
  const chemin: Op[] = [];
  while (par[i][j] !== null) {
    const op = par[i][j] as Op;
    chemin.push(op);
    if (op === "MATCH") { i--; j--; }
    else if (op === "INSERT") j--;
    else i--;
  }
  return chemin.reverse(); // l'ordre était inversé
}

La fonction calcule le coût de l'alignement optimal ; la reconstruction (path reconstruction) suit les pointeurs parent depuis la cellule but (n, m) jusqu'à la cellule initiale (0, 0). Transformer « thou shalt not » en « you should not » coûte cinq moves, et le backtrack révèle la séquence exacte d'opérations.

Une matrice, mille usages

La beauté de la distance d'édition : de nombreux problèmes en sont des cas particuliers, obtenus en changeant quelques fonctions de coût.

• Recherche de sous-chaîne approchée — pour trouver où « Skiena » apparaît (même mal orthographié) dans un long texte, on initialise la ligne 0 à coût nul (commencer le match n'importe où est gratuit) et la cellule but devient l'endroit le moins cher où le motif s'achève.
• Plus longue sous-séquence commune (longest common subsequence, LCS) — pour ne garder que les caractères communs aux deux chaînes, on interdit la substitution en lui donnant un coût prohibitif. La LCS de « democrat » et « republican » est « eca ». Seules les insertions/suppressions restent, et l'alignement de coût minimal préserve la plus longue sous-séquence partagée.
• Plus longue sous-séquence croissante (maximum monotone subsequence) — c'est une LCS entre la suite S et la même suite triée par ordre croissant.

Plus longue sous-séquence croissante, depuis zéro

Skiena recommande de la travailler à la main, « car ces algorithmes sont souvent plus faciles à réinventer qu'à retrouver ». Pour S = {2, 4, 3, 5, 1, 7, 6, 9, 8}, la plus longue sous-séquence croissante a une longueur de 5, par exemple {2, 3, 5, 6, 8}.

La bonne question : que faut-il savoir sur les n-1 premiers éléments pour conclure ? Connaître la longueur maximale ne suffit pas. Il faut la longueur de la plus longue suite que chaque valeur possible peut prolonger. On définit donc l[i] = longueur de la plus longue suite croissante se terminant exactement sur s[i].

l[i] = 1 + max{ l[j] : j < i et s[j] < s[i] }   (0 si aucun j)

La réponse globale est max(l[i]), car la suite gagnante se termine bien quelque part.

// O(n²) temps, O(n) espace. Renvoie la sous-séquence elle-même.
function plusLongueCroissante(s: number[]): number[] {
  const n = s.length;
  const longueur = new Array(n).fill(1);
  const pred = new Array(n).fill(-1); // prédécesseur de chacun
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (s[j] < s[i] && longueur[j] + 1 > longueur[i]) {
        longueur[i] = longueur[j] + 1;
        pred[i] = j;
      }
    }
  }
  let fin = 0;
  for (let i = 1; i < n; i++) if (longueur[i] > longueur[fin]) fin = i;
  const resultat: number[] = [];
  for (let k = fin; k !== -1; k = pred[k]) resultat.push(s[k]);
  return resultat.reverse();
}

On stocke pour chaque élément son prédécesseur pred[i], ce qui permet de reconstruire la suite en remontant les pointeurs depuis le dernier élément. Le coût est O(n²) ; une astuce de dictionnaire le ramène à O(n log n), mais la version simple est un bon point de départ.

Au-delà des chaînes : partition, parsing, triangulation

La même machinerie résout des problèmes apparemment éloignés, du moment qu'ils possèdent un ordre gauche-droite.

• Partition linéaire — répartir une séquence de n nombres en k tranches sans réordonner, pour minimiser la somme maximale d'une tranche (équilibrage de charge sur k processeurs). On définit M[n][k] et l'on choisit où placer le dernier diviseur. Une heuristique qui vise la moyenne échoue sur certaines entrées, car elle n'évalue pas systématiquement toutes les possibilités. La récurrence, elle, donne l'optimum en O(kn²) grâce aux sommes préfixes.
• Analyse syntaxique (parsing) d'une grammaire non contextuelle (en forme normale de Chomsky) — M[i][j][X] est vrai si la sous-chaîne S[i..j] est engendrée par le non-terminal X. On teste tous les points de coupure k. C'est l'algorithme CKY, en O(n³). Sa généralisation à la distance d'édition trouve même le nombre minimal de substitutions pour rendre un programme syntaxiquement correct.
• Triangulation de poids minimal d'un polygone convexe — chaque arête appartient à exactement un triangle ; choisir le troisième sommet partage le polygone en deux sous-pièces. O(n³) temps, O(n²) espace.

Quand la programmation dynamique échoue

Elle ne fonctionne pas toujours, et il est crucial de comprendre pourquoi. Prenons le plus long chemin simple (longest simple path) entre deux sommets s et t, qui ne visite aucun sommet deux fois — une variante du voyageur de commerce.

On serait tenté de poser LP[i][j] = max{ LP[i][x] + c(x,j) } sur toutes les arêtes (x, j). Deux problèmes rédhibitoires :

1. La récurrence n'impose pas la simplicité. Rien ne garantit que j n'apparaissait pas déjà sur le chemin de i à x ; ajouter l'arête créerait un cycle.
2. Aucun ordre d'évaluation. Faute d'ordre gauche-droite ou petit-vers-grand sur les sommets d'un graphe quelconque, on ne sait pas quels sont les « sous-problèmes plus petits ». On tourne en boucle infinie.

Le principe d'optimalité

La programmation dynamique exige le principe d'optimalité (principle of optimality), pilier de la sous-structure optimale : une solution partielle peut être étendue de façon optimale en ne considérant que l'état atteint, pas la séquence précise de décisions qui y a mené. Pour la distance d'édition, peu importe quelle suite d'opérations a atteint le coût C ; seul le coût compte. Le principe est violé quand les spécificités des opérations importent, et non leur seul coût.

Pour rendre le plus long chemin simple correct, il faut faire de l'ensemble des sommets déjà visités une partie de l'état : LP[i][j][S]. Mais il y a 2^n sous-ensembles ! C'est mieux que les n! tournées énumérées par la recherche exhaustive — assez pour résoudre des TSP jusqu'à une trentaine de sommets — mais cela reste exponentiel.

L'optimum global vaut le détour

Trois war stories de Skiena montrent la DP à l'œuvre : le morphing d'images (transformer un homard en homme en alignant des lignes de pixels, des intervalles ne pouvant se croiser), la minimisation de trie pour l'unification en Prolog (l'ordre imposé des règles, qui rendait le problème NP-complet sans lui, est précisément ce qui permettait une récurrence efficace, avec 20 % de gain sur la version gloutonne), et la compression de codes-barres PDF-417 (encoder un texte en minimisant les changements de mode, O(n) par programmation dynamique, soit 8 % de capacité gagnée en moyenne sur 13 000 étiquettes).

À retenir

• DP = exhaustivité (correction) + mémorisation (efficacité) : on part toujours d'une récurrence correcte, puis on évite les recalculs.
• Deux conditions indispensables : des sous-problèmes qui se recouvrent (sinon la mémoïsation ne sert à rien) et une sous-structure optimale respectant le principe d'optimalité.
• Trois implémentations : récursif naïf (souvent exponentiel) → mémoïsation top-down (cache) → tabulation bottom-up (remplir une table, parfois en espace constant).
• Tout l'art est dans la récurrence : raisonner sur le dernier élément, borner le nombre d'états par un polynôme, choisir un ordre d'évaluation valide.
• La reconstruction de la solution (et pas seulement de son coût) se fait par backtrack dans la table, via des pointeurs parent ou prédécesseur.
• DP excelle sur les objets ordonnés de gauche à droite (chaînes, suites, polygones) ; sans cet ordre — plus long chemin simple, TSP général — l'espace d'états explose et la technique ne sauve plus rien.