La programmation dynamique

1. De la récursivité naïve à la programmation dynamique

Partons d'un exemple familier : la suite de Fibonacci, définie par F₀ = 0, F₁ = 1 et F_n = F_n−1 + F_n−2. La traduction récursive directe est immédiate :

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Cette fonction est correcte, mais catastrophiquement lente. Pour calculer fib(5), elle appelle fib(4) et fib(3) ; or fib(4) rappelle fib(3)… Le même sous-problème est recalculé encore et encore. Le nombre d'appels croît comme F_n lui-même, soit de façon exponentielle : la complexité est en \(O(\varphi ^{n})\) avec \(\varphi \approx 1{,}618\).

L'idée de la programmation dynamique tient en une phrase : « ne jamais recalculer deux fois la même chose ». On mémorise le résultat de chaque sous-problème la première fois qu'on le rencontre, et on le réutilise ensuite. La complexité tombe alors de \(O(\varphi ^{n})\) à \(O(n)\) : c'est tout l'intérêt annoncé par le programme — réduire la complexité temporelle.

2. Les deux ingrédients

La programmation dynamique ne s'applique pas à n'importe quel problème. Il en faut deux propriétés.

Lien avec les algorithmes gloutons. La sous-structure optimale est commune aux deux approches. La différence est dans le choix : un glouton fait un seul choix (le plus prometteur) et ne le remet jamais en cause ; la programmation dynamique examine tous les choix possibles à chaque étape et garde le meilleur. La PD est donc plus coûteuse mais toujours optimale — elle résout exactement les problèmes où le glouton échoue (comme le sac à dos 0/1).

2.1 — La méthode : extraire la formule de récurrence

Le cœur du travail, en programmation dynamique, est de trouver la relation de récurrence. La démarche est toujours la même :

1. définir précisément ce que désigne le sous-problème (l'état) ;
2. écrire les cas de base (les plus petits sous-problèmes, résolus directement) ;
3. exprimer la solution d'un sous-problème en fonction de sous-problèmes plus petits (le « cas général ») ;
4. identifier la réponse finale parmi les sous-problèmes calculés.

3. Les deux approches : Top-Down et Bottom-Up

Une fois la récurrence écrite, deux manières de la mettre en œuvre. Elles donnent le même résultat avec la même complexité ; elles diffèrent par le sens du calcul.

3.1 — Top-Down : la mémoïsation

On garde la formulation récursive naturelle (« de haut en bas », du gros problème vers les petits), mais on ajoute un cache (dictionnaire ou tableau) : avant de calculer, on regarde si le résultat est déjà connu ; après l'avoir calculé, on le range dans le cache.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:                # déjà calculé : on réutilise
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

3.2 — Bottom-Up : la tabulation

On part au contraire des plus petits sous-problèmes (« de bas en haut ») et on remplit un tableau dans le bon ordre, jusqu'au problème complet. Aucune récursion : juste des boucles.

def fib_tab(n):
    if n < 2:
        return n
    f = [0] * (n + 1)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i-1] + f[i-2]   # les deux cases sont déjà remplies
    return f[n]

4. Le sac à dos 0/1

Problème. n objets, chacun de poids p_i et de valeur v_i ; un sac de capacité C. Chaque objet est pris en entier ou pas du tout. Maximiser la valeur totale sans dépasser C. (On a vu au chapitre précédent que le glouton échoue ici : la PD donne la solution exacte.)

État. Soit M(i, c) = la valeur maximale atteignable en n'utilisant que les i premiers objets avec une capacité c. La réponse cherchée est M(n, C).

Récurrence. Pour décider du sort de l'objet i, deux possibilités :

Le max compare les deux décisions : ne pas prendre l'objet i (on garde M(i−1, c)) ou le prendre (on gagne v_i mais on perd p_i de capacité). C'est exactement le « examiner tous les choix » de la programmation dynamique.

def sac_a_dos(poids, valeurs, C):
    n = len(poids)
    M = [[0] * (C + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(C + 1):
            if poids[i-1] > c:
                M[i][c] = M[i-1][c]
            else:
                M[i][c] = max(M[i-1][c],
                             valeurs[i-1] + M[i-1][c - poids[i-1]])
    return M[n][C]

On remplit le tableau M de taille \((n+1) \times (C+1)\), d'où une complexité en \(O(n \cdot C)\). C'est ce qu'on appelle une complexité pseudo-polynomiale (elle dépend de la valeur C, pas seulement du nombre d'objets). Pour C = 50 et les objets A(60,10), B(100,20), C(120,30) du contre-exemple glouton, on obtient bien la valeur optimale 220 (B + C), là où le glouton donnait 160.

5. La plus longue sous-séquence commune (PLSSC)

Problème. Une sous-séquence d'une chaîne s'obtient en supprimant des caractères sans changer l'ordre des restants (ils ne sont pas forcément contigus). Étant données deux chaînes X et Y, trouver la longueur de leur plus longue sous-séquence commune. Exemple : pour ABCBDAB et BDCAB, la PLSSC est BCAB, de longueur 4. (En anglais : LCS, Longest Common Subsequence ; utilisé par diff, Git, la bio-informatique…)

État. Soit L(i, j) = la longueur de la PLSSC des i premiers caractères de X et des j premiers caractères de Y.

Quand les deux derniers caractères coïncident, ils font partie de la sous-séquence commune : on les prend et on continue sur le reste. Sinon, on essaie de retirer le dernier caractère de l'une ou de l'autre chaîne, et on garde le meilleur des deux essais.

def plssc(X, Y):
    n, m = len(X), len(Y)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[n][m]

Complexité \(O(n \cdot m)\) (produit des longueurs), au lieu de l'explosion exponentielle d'une recherche naïve sur toutes les sous-séquences.

6. La distance de Levenshtein (distance d'édition)

Problème. Combien d'opérations élémentaires faut-il, au minimum, pour transformer une chaîne X en une chaîne Y ? Les opérations autorisées sont : insérer un caractère, supprimer un caractère, substituer un caractère par un autre (chacune coûte 1). C'est le cœur des correcteurs orthographiques et de la suggestion « vouliez-vous dire… ? ».

État. Soit D(i, j) = le nombre minimal d'opérations pour transformer les i premiers caractères de X en les j premiers caractères de Y.

def levenshtein(X, Y):
    n, m = len(X), len(Y)
    D = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        D[i][0] = i
    for j in range(m + 1):
        D[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if X[i-1] == Y[j-1]:
                D[i][j] = D[i-1][j-1]
            else:
                D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1])
    return D[n][m]

Complexité \(O(n \cdot m)\). Par exemple, la distance entre CHIEN et NICHE se calcule en remplissant un tableau \(6 \times 6\). La même structure de récurrence (sur deux indices, avec un min/max) revient dans tous les problèmes « sur deux chaînes » : c'est un patron à reconnaître.

7. Récapitulatif

CPGE MP/PSI — Informatique · Chapitre : La programmation dynamique · Conforme au programme officiel 2023