Programmation dynamique : principe et exemples

La programmation dynamique a mauvaise réputation : elle passe pour une astuce obscure réservée aux compétiteurs. En réalité, c'est une seule idée, simple et redoutable : ne jamais résoudre deux fois le même sous-problème. Dès qu'un calcul se répète — et il se répète souvent — on le mémorise et on le réutilise. C'est ce qui fait passer un algorithme d'un temps exponentiel à un temps linéaire.

Cet article te donne tout ce qu'il faut pour la maîtriser en prépa : le principe (sous-problèmes qui se chevauchent + sous-structure optimale), les deux implémentations (mémoïsation top-down et table bottom-up), les quatre exemples canoniques attendus en MPI — Fibonacci, rendu de monnaie, plus longue sous-séquence commune et sac à dos — avec code Python commenté, et 3 exercices corrigés. Nos profs Hadamard, anciens de MP2I et de MPSI option info passés par l'X, l'ENS et CentraleSupélec, voient chaque année les mêmes blocages : ils les listent pour que tu les évites.

Le principe : deux conditions à réunir

La programmation dynamique s'applique à un problème d'optimisation (ou de comptage) lorsque deux propriétés sont réunies. Ce sont les deux cases à cocher avant de dérouler la méthode.

Toute la difficulté d'un exercice de programmation dynamique tient dans une seule étape : trouver la relation de récurrence et bien définir ce que représente chaque sous-problème. Une fois cette relation posée, le code s'écrit presque mécaniquement, dans un sens ou dans l'autre.

Mémoïsation (top-down) ou table (bottom-up)

Une fois la récurrence trouvée, il reste à la calculer sans redondance. Deux stratégies, exactement la même complexité, deux styles de code.

La mémoïsation (top-down, « du haut vers le bas ») garde l'écriture récursive naturelle. On part du problème complet, on descend vers les sous-problèmes, et on range chaque résultat dans un cache (dictionnaire ou tableau). Avant chaque calcul, on regarde si la réponse est déjà connue : si oui, on la relit ; sinon, on la calcule puis on la stocke.

La table (bottom-up, « du bas vers le haut ») renverse le sens. On part des plus petits sous-problèmes, on remplit un tableau de proche en proche selon la récurrence, jusqu'à atteindre le problème demandé. Pas de récursion, donc aucun risque de débordement de pile.

Les deux approches reposent sur la récursivité et sur l'analyse de complexité ; garde les deux en tête, un même exercice se traite souvent des deux manières.

Fibonacci : de l'exponentiel au linéaire

La suite de Fibonacci est l'exemple fondateur. Elle est définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$. La traduction récursive naïve est immédiate :

def fib(n):
    # Version naive : traduit directement la recurrence.
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Le problème n'est pas la justesse mais le coût. Pour calculer fib(n), on relance fib(n-1) et fib(n-2), qui relancent à leur tour deux appels chacun. Le même sous-calcul est refait un nombre gigantesque de fois : fib(5) recalcule fib(2) trois fois. Le nombre d'appels croît comme une exponentielle, en $O(2^n)$ environ (plus précisément en $O(\varphi^n)$ où $\varphi$ est le nombre d'or). Dès $n = 40$, la machine peine.

C'est le cas d'école de sous-problèmes qui se chevauchent. On mémoïse : chaque $F_k$ n'est calculé qu'une fois, puis relu dans un cache.

def fib_memo(n, memo=None):
    # Version top-down : recursion + cache.
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:              # deja calcule : on relit
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Chaque valeur de $0$ à $n$ est désormais calculée une seule fois : le temps devient linéaire, en $O(n)$, pour un coût mémoire $O(n)$. La version table (bottom-up) donne le même résultat sans récursion :

def fib_table(n):
    # Version bottom-up : on remplit un tableau des petits vers les grands.
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # recurrence appliquee dans l'ordre
    return dp[n]

Rendu de monnaie : le nombre minimal de pièces

Problème. On dispose d'un système de pièces (par exemple $1$, $3$, $4$) en quantité illimitée. Pour un montant donné, quel est le nombre minimal de pièces pour l'atteindre exactement ?

L'algorithme glouton (prendre à chaque fois la plus grosse pièce possible) semble naturel, mais il échoue sur certains systèmes. La sous-structure optimale, elle, est nette : si $m(s)$ est le nombre minimal de pièces pour le montant $s$, alors en essayant chaque pièce $p$ en dernière position :

On remplit une table de $0$ jusqu'au montant visé :

def rendu_monnaie(pieces, montant):
    # dp[s] = nombre minimal de pieces pour rendre exactement s.
    INF = float('inf')
    dp = [0] + [INF] * montant          # dp[0] = 0, le reste inconnu
    for s in range(1, montant + 1):
        for p in pieces:
            if p <= s and dp[s - p] + 1 < dp[s]:
                dp[s] = dp[s - p] + 1   # une piece p de plus que dp[s - p]
    return dp[montant] if dp[montant] != INF else -1   # -1 = impossible

La complexité est $O(\text{montant} \times \text{nombre de pièces})$ : chaque case du tableau teste chaque pièce. Sur l'exemple pièces $\lbrace 1, 3, 4 \rbrace$ et montant $6$, le glouton propose $4 + 1 + 1 = 3$ pièces, alors que la table trouve $3 + 3 = 2$ pièces — l'optimum. On le vérifie en exercice.

Plus longue sous-séquence commune

Problème. Étant donné deux chaînes, quelle est la longueur de leur plus longue sous-séquence commune (PLSSC, ou LCS) ? Une sous-séquence garde l'ordre des caractères mais autorise des trous : ACE est une sous-séquence de ABCDE. C'est le principe des outils de comparaison de fichiers et de séquences ADN.

Tester toutes les sous-séquences serait exponentiel, en $O(2^n)$. La récurrence dynamique compare les chaînes $A$ et $B$ caractère par caractère. On note $L(i, j)$ la PLSSC des $i$ premiers caractères de $A$ et des $j$ premiers de $B$ :

def plssc(a, b):
    n, m = len(a), len(b)
    # dp[i][j] = longueur de la PLSSC de a[:i] et b[:j].
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:        # dernier caractere commun
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:                           # on ecarte l'un des deux
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

On remplit un tableau à deux dimensions de taille $(n+1) \times (m+1)$ : la complexité est $O(n \times m)$, à comparer à l'explosion exponentielle de la recherche naïve. La réponse se lit dans la dernière case, dp[n][m].

Le sac à dos (knapsack)

Problème. On a $n$ objets, chacun de poids $w_i$ et de valeur $v_i$, et un sac de capacité $C$. Quelle est la valeur maximale qu'on peut emporter sans dépasser $C$ ? Ici, chaque objet se prend ou se laisse (sac à dos 0/1) : on ne coupe pas un objet en deux.

Essayer toutes les parties des objets, c'est $2^n$ possibilités. La récurrence dynamique raisonne objet par objet. On note $K(i, c)$ la valeur maximale atteignable avec les $i$ premiers objets et une capacité $c$. Pour l'objet $i$, deux choix : le laisser, ou le prendre s'il tient :

def sac_a_dos(poids, valeurs, capacite):
    n = len(poids)
    # dp[i][c] = valeur max avec les i premiers objets et capacite c.
    dp = [[0] * (capacite + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(capacite + 1):
            dp[i][c] = dp[i - 1][c]                 # objet i-1 laisse
            if poids[i - 1] <= c:                   # objet i-1 pris s'il tient
                pris = dp[i - 1][c - poids[i - 1]] + valeurs[i - 1]
                dp[i][c] = max(dp[i][c], pris)
    return dp[n][capacite]

3 exercices corrigés

Exercice 1, monter un escalier

Énoncé. Un escalier a $n$ marches. À chaque pas, on monte de $1$ ou $2$ marches. Combien y a-t-il de façons différentes d'atteindre la marche $n$ ? Donner la récurrence, puis une version en $O(n)$.

Solution. Pour atteindre la marche $n$, le dernier pas vient soit de la marche $n-1$ (pas de $1$), soit de la marche $n-2$ (pas de $2$). Le nombre de chemins $c(n)$ vérifie donc :

C'est exactement la suite de Fibonacci (décalée) : les sous-problèmes se chevauchent, on remplit une table plutôt que de recalculer.

def escalier(n):
    # c[k] = nombre de facons d'atteindre la marche k.
    if n <= 1:
        return 1
    c = [0] * (n + 1)
    c[0], c[1] = 1, 1
    for k in range(2, n + 1):
        c[k] = c[k - 1] + c[k - 2]
    return c[n]

La version naïve récursive serait en $O(2^n)$ ; celle-ci est en $O(n)$ temps et $O(n)$ mémoire (réductible à $O(1)$ avec deux variables). Pour $n = 5$ : $c(5) = 8$ façons.

Exercice 2, rendu de monnaie et échec du glouton

Énoncé. Avec les pièces $\lbrace 1, 3, 4 \rbrace$, rendre la monnaie sur $6$. Montrer que l'algorithme glouton n'est pas optimal, puis dérouler la table dynamique.

Solution. Le glouton prend d'abord la plus grosse pièce $\le 6$, soit $4$, puis $1$, puis $1$ : total $4 + 1 + 1 = 3$ pièces. Or on peut faire $3 + 3 = 2$ pièces. Le glouton se trompe. On remplit $dp[s] = 1 + \min_{p \le s} dp[s-p]$ :

Lecture : $dp[3] = 1 + dp[0] = 1$ (une pièce de $3$), $dp[6] = 1 + \min(dp[5], dp[3], dp[2]) = 1 + dp[3] = 2$. La table confirme le minimum de $2$ pièces, là où le glouton en donnait $3$.

Exercice 3, remplir la table du sac à dos

Énoncé. Trois objets de poids $\lbrace 1, 2, 3 \rbrace$ et de valeurs $\lbrace 6, 10, 12 \rbrace$, un sac de capacité $C = 5$. Remplir la table $K(i, c)$ et donner la valeur maximale.

Solution. On applique $K(i, c) = \max\big(K(i-1, c),\ K(i-1, c - w_i) + v_i\big)$ ligne par ligne (l'objet $i$ ayant poids $w_i$ et valeur $v_i$). La ligne $0$ est nulle.

La valeur maximale est $K(3, 5) = 22$, obtenue en prenant les objets $2$ et $3$ (poids $2 + 3 = 5$, valeur $10 + 12 = 22$). On retrouve ce résultat en remontant la table : $K(3,5)$ vient de $K(2, 5-3) + 12 = K(2,2) + 12 = 10 + 12 = 22$.

Ce qu'il faut retenir

• Deux conditions : sous-problèmes qui se chevauchent + sous-structure optimale. Sans chevauchement, c'est du « diviser pour régner », pas de la programmation dynamique.
• Le vrai travail est de trouver la relation de récurrence et de bien définir chaque sous-problème ; le code suit presque mécaniquement.
• Deux implémentations : mémoïsation (top-down, récursif + cache) et table (bottom-up, itératif). Même complexité ; la table évite le débordement de pile.
• Le gain type : Fibonacci passe de $O(2^n)$ à $O(n)$. Rendu de monnaie en $O(\text{montant} \times \text{pièces})$, PLSSC en $O(n \times m)$, sac à dos en $O(n \times C)$.
• Le réflexe glouton ne donne pas toujours l'optimum : le rendu de monnaie le prouve. La programmation dynamique, elle, garantit l'optimum sous sous-structure optimale.

La programmation dynamique s'appuie directement sur la récursivité et sur la notation de complexité ; elle prolonge naturellement les algorithmes classiques de tri et de recherche vus en début de prépa.

C'est l'un des chapitres phares de l'informatique de deuxième année, en particulier pour ceux qui poussent l'option info. Pour situer sa place dans le cursus, vois pourquoi choisir l'option informatique en MPSI, une porte d'entrée vers la filière MPI où la programmation dynamique est centrale.