Chapitre 8 - Partie 3 : Programmation dynamique

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Programmation dynamique.	Utiliser la programmation dynamique pour écrire un algorithme.	Les exemples de l'alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée.

1. Le problème des sous-problèmes chevauchants

1.1 Retour sur Fibonacci récursif

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

Pour calculer fib(5), on observe une explosion des appels :

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(2) est calculé 3 fois, fib(3) est calculé 2 fois. Le nombre total d'appels croît exponentiellement : O(2ⁿ).

1.2 L'idée de la programmation dynamique

La programmation dynamique résout ce problème en mémorisant les résultats déjà calculés pour ne pas les recalculer. Deux approches existent :

Approche	Principe	Direction
Descendante (mémoïsation)	Récursion + stockage des résultats	Du problème vers les cas de base
Ascendante (tabulation)	Remplissage d'un tableau de bas en haut	Des cas de base vers le problème

2. Fibonacci optimisé

2.1 Approche descendante (mémoïsation)

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

2.2 Approche ascendante (tabulation)

def fib_tab(n):
    if n <= 1:
        return n
    tab = [0] * (n + 1)
    tab[1] = 1
    for i in range(2, n + 1):
        tab[i] = tab[i - 1] + tab[i - 2]
    return tab[n]

2.3 Comparaison des complexités

Version	Temps	Mémoire
Récursive naïve	O(2ⁿ)	O(n) (pile)
Mémoïsation	O(n)	O(n) (dictionnaire)
Tabulation	O(n)	O(n) (tableau)

3. Le rendu de monnaie

3.1 Le problème

On dispose d'un système de pièces (par exemple {1, 2, 5, 10}) et on veut rendre une somme donnée avec le minimum de pièces.

En première, on a vu l'algorithme glouton (prendre la plus grande pièce possible). Mais le glouton ne donne pas toujours la solution optimale (exemple : pièces {1, 3, 4}, somme 6 → glouton donne 4+1+1 = 3 pièces, optimal = 3+3 = 2 pièces).

3.2 Solution par programmation dynamique

On construit un tableau nb_pieces[s] = nombre minimal de pièces pour rendre la somme s.

Relation de récurrence :

$\text{nb\_pieces}[s] = 1 + \min_{p \in \text{pieces}} \text{nb\_pieces}[s - p] \quad \text{pour } s - p \geq 0$

def rendu_monnaie(pieces, somme):
    nb_pieces = [float('inf')] * (somme + 1)
    nb_pieces[0] = 0

    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s and nb_pieces[s - p] + 1 < nb_pieces[s]:
                nb_pieces[s] = nb_pieces[s - p] + 1

    return nb_pieces[somme]

>>> rendu_monnaie([1, 3, 4], 6)
2    # 3 + 3
>>> rendu_monnaie([1, 2, 5, 10], 13)
3    # 10 + 2 + 1

3.3 Retrouver la décomposition

Pour connaître les pièces utilisées, on mémorise les choix :

def rendu_monnaie_detail(pieces, somme):
    nb_pieces = [float('inf')] * (somme + 1)
    nb_pieces[0] = 0
    dernier_choix = [0] * (somme + 1)

    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s and nb_pieces[s - p] + 1 < nb_pieces[s]:
                nb_pieces[s] = nb_pieces[s - p] + 1
                dernier_choix[s] = p

    # Reconstruction de la solution
    resultat = []
    s = somme
    while s > 0:
        resultat.append(dernier_choix[s])
        s -= dernier_choix[s]
    return resultat

>>> rendu_monnaie_detail([1, 3, 4], 6)
[3, 3]

4. Alignement de séquences

4.1 Le problème

En bioinformatique, on compare des séquences d'ADN ou de protéines en cherchant le meilleur alignement : faire correspondre les caractères de deux séquences en insérant éventuellement des « trous » (gaps, notés -).

Exemple : aligner ACTG et ACG :

A C T G
A C - G

4.2 Distance d'édition

La distance d'édition (ou distance de Levenshtein) entre deux chaînes est le nombre minimal d'opérations élémentaires pour transformer l'une en l'autre :

Insertion d'un caractère ;
Suppression d'un caractère ;
Substitution d'un caractère par un autre.

4.3 Solution par programmation dynamique

On construit un tableau d[i][j] = distance d'édition entre les i premiers caractères de la chaîne 1 et les j premiers caractères de la chaîne 2.

def distance_edition(s1, s2):
    n, m = len(s1), len(s2)
    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):
            cout = 0 if s1[i-1] == s2[j-1] else 1
            d[i][j] = min(
                d[i-1][j] + 1,       # suppression
                d[i][j-1] + 1,       # insertion
                d[i-1][j-1] + cout   # substitution (ou correspondance)
            )

    return d[n][m]

>>> distance_edition("ACTG", "ACG")
1    # une suppression (le T)
>>> distance_edition("chat", "chien")
3    # a→i, t→e, +n

4.4 Complexité

Temps : O(n × m) où n et m sont les longueurs des chaînes ;
Mémoire : O(n × m) pour le tableau (peut être réduit à O(min(n, m)) si on n'a besoin que de la distance).

5. Quand utiliser la programmation dynamique ?

Condition	Description
Sous-structure optimale	La solution optimale contient les solutions optimales des sous-problèmes
Chevauchement	Les mêmes sous-problèmes sont résolus plusieurs fois

À retenir

Concept	Description
Programmation dynamique	Mémoriser les résultats pour éviter les recalculs
Mémoïsation	Approche descendante (récursion + cache)
Tabulation	Approche ascendante (remplissage d'un tableau)
Rendu de monnaie	Nombre minimal de pièces, optimal contrairement au glouton
Distance d'édition	Nombre minimal d'opérations pour transformer une chaîne en une autre
Sous-problèmes chevauchants	Condition nécessaire pour que la prog. dynamique soit utile