Programmation dynamique

2. Exemple canonique — Fibonacci

La suite de Fibonacci est définie par $F_0=0$, $F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour $n\ge 2$. C'est le terrain d'entraînement idéal : la récurrence est immédiate, mais la traduire naïvement en récursion est un désastre.

2.1 La version récursive naïve est exponentielle

def fib_naif(n):
    if n <= 1:          # cas de base : F0 = 0 et F1 = 1
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

Regarde ce qui se passe pour calculer $F_5$ : l'arbre des appels recalcule $F_3$ deux fois, $F_2$ trois fois, $F_1$ cinq fois… Le nombre d'appels double presque à chaque niveau : la complexité est exponentielle, en $O({\phi }^n)$ avec $\phi \approx 1,618$ (grosso modo $O(2^n)$). Dès $n=40$, la machine rame.

Total : 15 appels pour $F_5$, et cela grossit de façon explosive. Tout ce travail est gâché car on recalcule sans cesse les mêmes valeurs : c'est exactement la situation où la mémoïsation change tout.

2.2 Version mémoïsée (top-down) : on passe au linéaire

def fib_memo(n, cache=None):
    if cache is None:       # au premier appel, on cree le dictionnaire vide
        cache = {}
    if n <= 1:              # cas de base inchange
        return n
    if n in cache:          # deja calcule ? on renvoie sans refaire le travail
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Maintenant chaque $F_k$ n'est calculé qu'une seule fois : on remplit le cache de $F_2$ jusqu'à $F_n$. Il y a $n$ valeurs à calculer, chacune en temps constant : la complexité tombe à $O(n)$ en temps (et $O(n)$ en mémoire pour le cache).

2.3 Version itérative (bottom-up)

On peut se passer de récursion : on remplit un tableau dp des petits indices vers les grands. C'est souvent plus rapide (pas de pile d'appels) et tout aussi simple ici.

def fib_iter(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)      # dp[i] contiendra F_i
    dp[1] = 1               # on initialise les cas de base
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

3. Exemple fort — le rendu de monnaie optimal

Rendre une somme $s$ avec un minimum de pièces, en piochant dans un système $[p_1,\dots ,p_k]$. L'algorithme glouton (prendre la plus grosse pièce possible) marche sur le système euro, mais échoue sur certains systèmes. La programmation dynamique, elle, donne toujours l'optimum.

3.1 La récurrence

Notons $dp[s]$ le nombre minimal de pièces pour rendre exactement la somme $s$. Sous-structure optimale : pour rendre $s$, la dernière pièce posée est une pièce $p\le s$, et il reste alors à rendre $s-p$ de façon optimale. On teste donc toutes les dernières pièces possibles et on garde la meilleure :

$$dp[0]=0,dp[s]=1+\underset{\begin{array}{c}p\in \text{pieˋces}\\ p\le s\end{array}}{\min }dp[s-p].$$

Le $+1$ compte la pièce $p$ qu'on vient de poser. Le $dp[0]=0$ dit qu'il faut 0 pièce pour rendre 0. Les sous-problèmes $dp[s-p]$ se chevauchent massivement d'une somme à l'autre : c'est bien de la programmation dynamique.

3.2 Le code (bottom-up)

def rendu_optimal(pieces, s):
    INF = float('inf')
    dp = [0] + [INF] * s           # dp[0]=0, le reste = infini (pas encore atteint)
    for m in range(1, s + 1):      # on remplit les sommes de 1 a s
        for p in pieces:           # on essaie chaque piece comme derniere posee
            if p <= m and dp[m - p] + 1 < dp[m]:
                dp[m] = dp[m - p] + 1
    return dp[s]

Lecture de la case $dp[6]$ : la meilleure dernière pièce est 3, donc $dp[6]=1+dp[3]=1+1=2$. La programmation dynamique rend 6 avec 2 pièces (3+3), là où le glouton en utilisait 3. Détail des cases clés : $dp[3]=1$ (une pièce de 3), $dp[4]=1$ (une pièce de 4), $dp[2]=2$ (1+1), $dp[5]=2$ (4+1).

3.3 Complexité

Deux boucles imbriquées : la somme $m$ va de 1 à $n$ ($n$ itérations), et pour chacune on parcourt les $k$ pièces. Le coût est donc $O(n\times k)$ en temps, où $n$ est la somme à rendre et $k$ le nombre de pièces. La mémoire est $O(n)$ pour le tableau dp. C'est bien plus fiable qu'un glouton : on paie un peu plus cher, mais on obtient toujours l'optimum.

4. Méthode — reconnaître un problème de programmation dynamique

5. Exercices corrigés

def escalier(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    if n >= 1:
        dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]