Programmation dynamique

Introduction

La programmation dynamique est une méthode qui s'applique aux problèmes dont la solution se décompose en sous-problèmes qui se chevauchent. Plutôt que de recalculer chaque sous-problème à chaque fois qu'on le rencontre, on mémorise son résultat. Cette idée simple transforme souvent un algorithme exponentiel en un algorithme polynomial.

C'est exactement la posture du caissier qui, pour rendre la monnaie, n'invente pas chaque fois la combinaison : il connaît déjà le rendu pour les petites sommes courantes et les combine. C'est aussi celle du joueur de Sudoku qui, plutôt que de tout recommencer, note dans chaque case les chiffres encore possibles — il mémorise ce qu'il a déjà déduit pour ne pas le redéduire à chaque coup.

Les deux conditions d'application

Un problème se prête à la programmation dynamique si :

1. Sous-structure optimale — la solution optimale du problème se construit à partir des solutions optimales de ses sous-problèmes.
2. Chevauchement des sous-problèmes — les mêmes sous-problèmes apparaissent plusieurs fois dans la résolution récursive naïve.

Sans la condition 2, diviser pour régner suffit (chaque sous-problème est unique). Avec la condition 2, on doit mémoriser pour ne pas exploser.

Exemple central : le rendu de monnaie

Problème : étant donné un système de pièces $P = \{p_1, p_2, \dots\}$ et une somme $n$, combien de pièces au minimum pour rendre exactement $n$ ?

Équation de récurrence :

Version récursive naïve — exponentielle

def rendre_naif(n, pieces):
    if n == 0: return 0
    return 1 + min(rendre_naif(n - p, pieces)
                   for p in pieces if p <= n)

Pour $n = 30$ et $P = \{1, 2, 5\}$, cet algorithme calcule des millions de fois les mêmes sous-problèmes. Son coût est exponentiel en $n$ — autant dire qu'il est inutilisable au-delà de $n \approx 25$.

Version mémoïsée — top-down

On ajoute un cache (un dictionnaire) qui mémorise les résultats déjà calculés.

def rendre_memo(n, pieces, cache=None):
    if cache is None:
        cache = {0: 0}
    if n in cache:
        return cache[n]
    cache[n] = 1 + min(rendre_memo(n - p, pieces, cache)
                       for p in pieces if p <= n)
    return cache[n]

Chaque valeur de $n$ entre $0$ et $n$ est calculée une seule fois, en $\mathcal{O}(|P|)$ par valeur. Coût total : $\mathcal{O}(n \cdot |P|)$ — polynomial.

Version tabulée — bottom-up

Au lieu de partir de $n$ et descendre récursivement, on construit un tableau dp[0..n] de bas en haut.

def rendre_tabule(n, pieces):
    INF = float('inf')
    dp = [0] + [INF] * n                # dp[0] = 0, le reste à infini
    for k in range(1, n + 1):
        for p in pieces:
            if p <= k and dp[k - p] + 1 < dp[k]:
                dp[k] = dp[k - p] + 1
    return dp[n]

Coût identique : $\mathcal{O}(n \cdot |P|)$. Mais on évite la récursion et on peut souvent réduire la mémoire : si seul dp[n] nous intéresse, parfois deux lignes suffisent (cf. plus loin).

Top-down vs bottom-up — le trade-off

Règle pratique : utiliser mémoïsation quand la récurrence est claire mais la tabulation peu intuitive ; tabulation quand on cherche à optimiser la mémoire ou à éviter la récursion profonde.

Le coût en mémoire — un levier essentiel

Beaucoup de problèmes de programmation dynamique peuvent voir leur mémoire réduite. Exemple : pour le plus court chemin sur une grille $m \times n$, la table de tailles $m \cdot n$ peut souvent être ramenée à deux lignes car chaque case ne dépend que de la ligne précédente ($\mathcal{O}(n)$ au lieu de $\mathcal{O}(mn)$).

def plus_court_chemin_grille(grille):
    """Coût minimal en partant du coin haut-gauche, en bas-droite, déplacements bas/droite."""
    m, n = len(grille), len(grille[0])
    precedente = [0] * n
    precedente[0] = grille[0][0]
    for j in range(1, n):
        precedente[j] = precedente[j-1] + grille[0][j]
    for i in range(1, m):
        courante = [0] * n
        courante[0] = precedente[0] + grille[i][0]
        for j in range(1, n):
            courante[j] = grille[i][j] + min(courante[j-1], precedente[j])
        precedente = courante
    return precedente[n-1]

Alignement de séquences — un survol

L'alignement de séquences est un problème central en bio-informatique : étant données deux chaînes (par exemple deux brins d'ADN), trouver l'alignement qui maximise le nombre de coïncidences en autorisant des insertions, des suppressions et des substitutions.

L'équation de récurrence sur le score $S(i, j)$ entre les préfixes de longueurs $i$ et $j$ est :

C'est exactement le schéma de programmation dynamique : on remplit une table $|a| \times |b|$ en $\mathcal{O}(|a| \cdot |b|)$. L'algorithme Needleman-Wunsch fait cela et a révolutionné l'analyse de génomes ; l'outil BLAST, utilisé quotidiennement par les biologistes pour comparer des séquences ADN à une banque de référence, en est une descendance directe.

Pour aller plus loin

La programmation dynamique est une technique très générale : elle s'applique au plus court chemin dans un DAG, à la distance d'édition (Levenshtein), au sac à dos (knapsack), à la multiplication de matrices chaînée, à de nombreuses questions de théorie des jeux… La difficulté n'est pas dans l'algorithme mais dans l'identification de la bonne récurrence.