Programmation dynamique ⚡

La programmation dynamique (DP) est une technique qui consiste à décomposer un problème en sous-problèmes et à mémoriser leurs solutions pour éviter de les recalculer. C'est l'une des techniques les plus puissantes en algorithmique.

---

1. Le problème fondamental : Fibonacci 🌀

Exécution pas à pas
pseudo
1/5
1FONCTION fib_naif(n)2    SI n ≤ 1 ALORS RETOURNER n        ⬅ Cas de base3    RETOURNER fib_naif(n-1) + fib_naif(n-2)  ⬅ Appels récursifs4FIN FONCTION                               ⬅ O(2^n) — exponentiel !5 
🧩
FONCTION fib_naif(n)
FONCTION fib_naif(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fib_naif(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Le problème : fib(5) appelle fib(4) et fib(3), fib(4) appelle fib(3) et fib(2) — on calcule fib(3) deux fois, fib(2) trois fois !

💡 La complexité explose : fib(50) nécessite ~2⁵⁰ = 1 quadrillion d'opérations !

---

2. Approche Top-Down (Mémoïsation) 📓

Idée : On garde un cache (dictionnaire). Avant de calculer, on vérifie si la valeur n'est pas déjà connue.

Exécution pas à pas
pseudo
1/12
1FONCTION fib_memo(n, memo ← {})2    SI n DANS memo ALORS3        RETOURNER memo[n]           ⬅ Déjà calculé → retour direct4    FIN SI5    SI n ≤ 1 ALORS6        memo[n] ← n                 ⬅ Cas de base7    SINON8        memo[n] ← fib_memo(n-1, memo) + fib_memo(n-2, memo)  ⬅ Calcul + stockage9    FIN SI10    RETOURNER memo[n]11FIN FONCTION                              ⬅ O(n) — linéaire !12 
🧩
FONCTION fib_memo(n, memo ← {})
FONCTION fib_memo(n, memo ← {})Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fib_memo(n, memo ← {})". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

# Naïf : O(2^n) — chaque appel crée deux branches
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# Mémoïsation : O(n) — chaque valeur calculée une seule fois
def fib_memo(n, 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]

Résultat : fib(50) passe de siècles à microsecondes ! Le cache transforme l'exponentiel en linéaire. [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765…]

---

3. Approche Bottom-Up (Tabulation) 📊

Idée : On remplit un tableau de bas en haut, du plus petit sous-problème au plus grand.

Exécution pas à pas
pseudo
1/9
1FONCTION fib_tab(n)2    SI n ≤ 1 ALORS RETOURNER n3    dp ← [0, 1]                          ⬅ Tableau des solutions4    POUR i ALLANT DE 2 À n FAIRE5        dp[i] ← dp[i-1] + dp[i-2]        ⬅ Chaque case dépend des deux précédentes6    FIN POUR7    RETOURNER dp[n]                       ⬅ O(n) — itératif8FIN FONCTION9 
🧩
FONCTION fib_tab(n)
FONCTION fib_tab(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fib_tab(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def fib_tab(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])  # Chaque nouveau = somme des deux précédents
    return dp[n]

Visualisation du tableau dp pour n=7 :

i	0	1	2	3	4	5	6	7
dp[i]	0	1	1	2	3	5	8	13

---

4. Problème classique : Sac à dos (Knapsack) 🎒

Énoncé : Tu as des objets avec un poids et une valeur. Ton sac a une capacité limitée. Quels objets emporter pour maximiser la valeur totale ?

Exécution pas à pas
pseudo
1/19
1FONCTION knapsack(poids, valeurs, capacité)2    n ← taille(poids)3    dp ← tableau[n+1][capacité+1] rempli de 0  ⬅ Tableau 2D4    5    POUR i ALLANT DE 1 À n FAIRE6        POUR w ALLANT DE 1 À capacité FAIRE7            SI poids[i-1] ≤ w ALORS           ⬅ L'objet tient dans le sac ?8                prendre ← valeurs[i-1] + dp[i-1][w - poids[i-1]]  ⬅ Prendre l'objet9                ne_pas_prendre ← dp[i-1][w]                       ⬅ Ne pas le prendre10                dp[i][w] ← MAX(prendre, ne_pas_prendre)11            SINON12                dp[i][w] ← dp[i-1][w]          ⬅ Trop lourd → on prend pas13            FIN SI14        FIN POUR15    FIN POUR16    17    RETOURNER dp[n][capacité]                 ⬅ Valeur maximale18FIN FONCTION19 
🧩
FONCTION knapsack(poids, valeurs, capacité)
FONCTION knapsack(poids, valeurs, capacité)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "knapsack(poids, valeurs, capacité)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def knapsack(poids, valeurs, capacite):
    n = len(poids)
    dp = [[0] * (capacite + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacite + 1):
            if poids[i - 1] <= w:
                dp[i][w] = max(
                    valeurs[i - 1] + dp[i - 1][w - poids[i - 1]],  # Prendre
                    dp[i - 1][w]                                     # Pas prendre
                )
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacite]

poids = [2, 3, 4, 5]
valeurs = [3, 4, 5, 6]
print(knapsack(poids, valeurs, 5))  # 7 (prendre objets 2+3 ou 4+1)

---

5. Plus longue sous-séquence commune (LCS) 🔤

Trouver la plus longue séquence de caractères commune à deux chaînes (dans l'ordre, pas forcément consécutifs).

Exécution pas à pas
pseudo
1/17
1FONCTION lcs(a, b)2    m ← taille(a), n ← taille(b)3    dp ← tableau[m+1][n+1] rempli de 04    5    POUR i ALLANT DE 1 À m FAIRE6        POUR j ALLANT DE 1 À n FAIRE7            SI a[i-1] == b[j-1] ALORS8                dp[i][j] ← dp[i-1][j-1] + 1    ⬅ Caractères identiques9            SINON10                dp[i][j] ← MAX(dp[i-1][j], dp[i][j-1])  ⬅ Prendre le meilleur des deux11            FIN SI12        FIN POUR13    FIN POUR14    15    RETOURNER dp[m][n]16FIN FONCTION17 
🧩
FONCTION lcs(a, b)
FONCTION lcs(a, b)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "lcs(a, b)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

print(lcs("ABCDEF", "ACDF"))  # 4 → "ACDF"

---

6. Distance d'édition (Levenshtein) ✏️

Nombre minimum d'opérations (insertion, suppression, substitution) pour transformer une chaîne en une autre.

Exécution pas à pas
pseudo
1/24
1FONCTION levenshtein(a, b)2    m ← taille(a), n ← taille(b)3    dp ← tableau[m+1][n+1]4    5    POUR i ALLANT DE 0 À m FAIRE dp[i][0] ← i    ⬅ Supprimer i caractères6    POUR j ALLANT DE 0 À n FAIRE dp[0][j] ← j    ⬅ Insérer j caractères7    8    POUR i ALLANT DE 1 À m FAIRE9        POUR j ALLANT DE 1 À n FAIRE10            SI a[i-1] == b[j-1] ALORS11                dp[i][j] ← dp[i-1][j-1]          ⬅ Rien à faire12            SINON13                dp[i][j] ← 1 + MIN(14                    dp[i-1][j],    ⬅ Suppression15                    dp[i][j-1],    ⬅ Insertion16                    dp[i-1][j-1]   ⬅ Substitution17                )18            FIN SI19        FIN POUR20    FIN POUR21    22    RETOURNER dp[m][n]23FIN FONCTION24 
🧩
FONCTION levenshtein(a, b)
FONCTION levenshtein(a, b)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "levenshtein(a, b)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

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

print(levenshtein("cheval", "chevalier"))  # 3 (ajouter i, e, r)

---

7. Chemin dans une grille avec obstacles 🧭

Compter le nombre de chemins uniques du coin supérieur gauche au coin inférieur droit, en évitant les obstacles (1 = bloqué).

Exécution pas à pas
pseudo
1/20
1FONCTION chemins_unique(grille)2    SI grille[0][0] == 1 ALORS RETOURNER 0     ⬅ Départ bloqué3    m ← lignes, n ← colonnes4    dp ← tableau[m][n] rempli de 05    dp[0][0] ← 1                                 ⬅ Un seul chemin pour commencer6    7    POUR i ALLANT DE 0 À m-1 FAIRE8        POUR j ALLANT DE 0 À n-1 FAIRE9            SI grille[i][j] == 1 ALORS10                dp[i][j] ← 0                     ⬅ Obstacle → aucun chemin11            SINON12                SI i > 0 ALORS dp[i][j] ← dp[i][j] + dp[i-1][j]  ⬅ Venir du haut13                SI j > 0 ALORS dp[i][j] ← dp[i][j] + dp[i][j-1]  ⬅ Venir de gauche14            FIN SI15        FIN POUR16    FIN POUR17    18    RETOURNER dp[m-1][n-1]19FIN FONCTION20 
🧩
FONCTION chemins_unique(grille)
FONCTION chemins_unique(grille)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "chemins_unique(grille)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def chemins_unique(grille):
    if not grille or grille[0][0] == 1:
        return 0
    m, n = len(grille), len(grille[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if grille[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0: dp[i][j] += dp[i - 1][j]
            if j > 0: dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]

grille = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(chemins_unique(grille))  # 2

---

Progression recommandée 🎯

1. Fibonacci avec mémoïsation — comprendre le cache (facile)
2. Sac à dos — découverte du tableau 2D (moyen)
3. LCS — manipulation de chaînes (moyen)
4. Distance d'édition — 3 opérations possibles (moyen-difficile)
5. Chemin dans une grille — obstacles et dénombrement (difficile)