Programmation dynamique
Progression
#Programmation dynamique
À quoi ça sert ?
À quoi ça sert: résoudre efficacement des problèmes avec sous‑problèmes qui se recoupent et structure optimale. Comment: définir une récurrence, choisir top‑down (mémoïsation) ou bottom‑up (tabulation), et décider l’ordre de calcul.
Objectifs d’apprentissage
- Reconnaître sous‑structures optimales et chevauchements.
- Choisir top‑down (mémoïsation) vs bottom‑up (tabulation) et l’ordre de calcul.
- Réduire l’espace (rolling arrays) et analyser la complexité temps/mémoire.
#Animation: de la récurrence à l’implémentation
Modéliser
Définir l’état et la récurrence
Top‑down
Mémoïsation (cache) si espace d’état parcimonieux
Bottom‑up
Tabulation si ordre clair
Espace
Rolling arrays / reconstruction
#Concepts clés
- Sous-structures optimales : La solution optimale d'un problème contient les solutions optimales de ses sous-problèmes.
- Chevauchement de sous-problèmes : Le même sous-problème est résolu plusieurs fois. La programmation dynamique stocke les résultats pour éviter les recalculs.
#Mémoïsation vs Tabulation
- Mémoïsation : Top-down. On utilise la récursion et on stocke les résultats dans une table.
- Tabulation : Bottom-up. On remplit un tableau de manière itérative.
#Fibonacci (mémoïsation)
Chargement de l’éditeur...
#Fibonacci (tabulation)
pythonpython
1def fib_tabulation(n):2 if n < 2:3 return n4 dp = [0] * (n + 1)5 dp[1] = 16 for i in range(2, n + 1):7 dp[i] = dp[i - 1] + dp[i - 2]8 return dp[n]9 10print([fib_tabulation(i) for i in range(12)])
Chargement de l’éditeur...
#Rendu de monnaie
Problème : Trouver le nombre minimal de pièces pour rendre une certaine somme.
pythonpython
1def coin_change(coins, amount):2 dp = [float('inf')] * (amount + 1)3 dp[0] = 04 for coin in coins:5 for x in range(coin, amount + 1):6 dp[x] = min(dp[x], dp[x - coin] + 1)7 return dp[amount] if dp[amount] != float('inf') else -18 9coins = [1, 3, 4]10amount = 611print(coin_change(coins, amount)) # 2 (3 + 3)
Chargement de l’éditeur...
#Sac à dos 0/1 (tabulation)
pythonpython
1def knap(values, weights, W):2 n = len(values)3 dp = [[0]*(W+1) for _ in range(n+1)]4 for i in range(1, n+1):5 for w in range(W+1):6 dp[i][w] = dp[i-1][w]7 if weights[i-1] <= w:8 dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])9 return dp[n][W]10 11values = [60, 100, 120]12weights = [10, 20, 30]13W = 5014print(knap(values, weights, W)) # 220
Chargement de l’éditeur...
#Exercices
- Chaîne de multiplication de matrices : Trouver le nombre minimal de multiplications scalaires nécessaires pour multiplier une chaîne de matrices.
- Plus longue sous-séquence commune (LCS) : Trouver la plus longue sous-séquence commune à deux chaînes.
- Nombre de chemins dans une grille : Trouver le nombre de chemins possibles dans une grille pour aller du coin supérieur gauche au coin inférieur droit.
#Exercice : Plus longue sous-séquence commune (LCS)
Implémentez l'algorithme de la plus longue sous-séquence commune (LCS) en utilisant la programmation dynamique.
Instructions
- Créez une matrice
dp
de taille(m+1) x (n+1)
oùm
etn
sont les longueurs des deux chaînes. - Initialisez la première ligne et la première colonne à 0.
- Pour chaque cellule
dp[i][j]
, si les caractères des deux chaînes sont égaux,dp[i][j] = dp[i-1][j-1] + 1
. Sinon,dp[i][j] = max(dp[i-1][j], dp[i][j-1])
. - La valeur
dp[m][n]
contiendra la longueur de la LCS.
Exemple de code
pythonpython
1def lcs(X, Y):2 m = len(X)3 n = len(Y)4 # Création de la matrice DP5 dp = [[0] * (n + 1) for _ in range(m + 1)]6 7 # Remplissage de la matrice8 for i in range(1, m + 1):9 for j in range(1, n + 1):10 if X[i - 1] == Y[j - 1]:11 dp[i][j] = dp[i - 1][j - 1] + 112 else:13 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])14
Chargement de l’éditeur...
Complexité
- Fibonacci (mémoïsation/tabulation): O(n).
- Rendu de monnaie: O(amount * nombre de pièces).
- Sac à dos 0/1: O(n * W).
- LCS: O(m * n).
#Pièges fréquents
- Mauvais ordre de remplissage en tabulation (dépendances non satisfaites).
- Mémoïsation sur espace d’état trop large sans prune → explosion.
- Transition ambiguë → doubles comptages.
#Mini‑quiz
La mémoïsation consiste à: