Programmation Dynamique
Le programme
La programmation dynamique est une méthode algorithmique permettant de résoudre efficacement des problèmes complexes en mémorisant les résultats des sous-problèmes déjà résolus.
Motivation : un problème de performance
Dans le chapitre Récursivité, vous avez écrit la fonction fibonacci suivante :
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
Et vous avez observé que l'arbre des appels contient de nombreux doublons :
fibonacci(5)
/ \
fibonacci(4) fibonacci(3) ← déjà calculé !
/ \ / \
fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
fibonacci(3) est calculé 2 fois, fibonacci(2) est calculé 3 fois, fibonacci(1) est calculé 5 fois.
La complexité de cet algorithme est exponentielle : O(2ⁿ). Pour fibonacci(50), cela représente plus de 1 000 milliards d'appels !
L'idée clé : si on avait mémorisé le résultat de fibonacci(3) lors du premier calcul, on n'aurait pas eu besoin de le recalculer.
L'idée clé : la programmation dynamique
Définition : La programmation dynamique est une méthode algorithmique qui consiste à :
- Décomposer un problème en sous-problèmes plus simples
- Mémoriser le résultat de chaque sous-problème pour éviter de le recalculer
- Combiner les résultats pour résoudre le problème initial
Il existe deux façons de mettre en œuvre cette idée :
| Approche | Principe | Autre nom |
|---|---|---|
| Top-down | On part du problème initial et on descend vers les sous-problèmes, en mémorisant au passage | Mémoïsation |
| Bottom-up | On commence par les sous-problèmes les plus simples et on remonte vers le problème initial | Tabulation |
Approche Top-Down : la mémoïsation
On garde la structure récursive, mais on ajoute un dictionnaire pour mémoriser les résultats déjà calculés. Avant chaque calcul, on vérifie si le résultat n'est pas déjà connu.
def fibonacci_memo(n):
memo = {}
memo[0] = 0
memo[1] = 1
def fib(k):
if k in memo: # si déjà calculé, on retourne directement
return memo[k]
memo[k] = fib(k-1) + fib(k-2) # sinon, on calcule et on mémorise
return memo[k]
return fib(n)
Avec fibonacci_memo(5), chaque valeur n'est calculée qu'une seule fois :
fib(5) → calcule fib(4) et fib(3)
fib(4) → calcule fib(3) et fib(2)
fib(3) → calcule fib(2) et fib(1) = 1 ✓ (mémorisé)
fib(2) → calcule fib(1) = 1 ✓ et fib(0) = 0 ✓ → mémorise fib(2) = 1
fib(3) → fib(2) = 1 ✓ (déjà en memo) + fib(1) = 1 ✓ → mémorise fib(3) = 2
fib(4) → fib(3) = 2 ✓ (déjà en memo) + fib(2) = 1 ✓ → mémorise fib(4) = 3
fib(5) → fib(4) = 3 ✓ + fib(3) = 2 ✓ → mémorise fib(5) = 5
La complexité passe de O(2ⁿ) à O(n) en temps, et O(n) en mémoire (pour stocker le dictionnaire).
Approche Bottom-Up : le tableau
On abandonne la récursion. On part des cas de base et on remplit un tableau dans l'ordre croissant jusqu'à atteindre la valeur souhaitée.
def fibonacci_bottom_up(n):
if n == 0:
return 0
tableau = [0] * (n + 1) # tableau[i] contiendra fibonacci(i)
tableau[0] = 0
tableau[1] = 1
for i in range(2, n + 1):
tableau[i] = tableau[i-1] + tableau[i-2]
return tableau[n]
Déroulement pour fibonacci_bottom_up(6) :
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| tableau[i] | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Chaque case est calculée exactement une fois, dans l'ordre. Complexité : O(n) en temps, O(n) en mémoire.
Remarque : On peut même optimiser l'espace mémoire à O(1) en ne gardant que les deux dernières valeurs, mais cette optimisation sort du programme.
Comparaison des trois approches
| Critère | Naïf (récursif) | Top-Down (mémoïsation) | Bottom-Up (tableau) |
|---|---|---|---|
| Style | Récursif | Récursif + dictionnaire | Itératif |
| Complexité temps | O(2ⁿ) | O(n) | O(n) |
| Complexité espace | O(n) pile d'appels | O(n) dictionnaire | O(n) tableau |
| Lisibilité | Très lisible | Lisible | Moins intuitif |
| Risque | RecursionError pour n grand | RecursionError pour n grand | Aucun |
En pratique, le bottom-up est souvent préféré en compétition et en entreprise car il évite les risques liés à la récursion. Le top-down est plus naturel quand on part d'une formule récursive.
À retenir
- La programmation dynamique = décomposer + mémoriser + combiner
- Elle s'applique quand un problème a des sous-problèmes qui se répètent
- Deux approches : top-down (mémoïsation, récursif) et bottom-up (tableau, itératif)
- Les deux ont une complexité polynomiale là où la version naïve est souvent exponentielle
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.