⚙️ Chapitre : La programmation dynamique
La programmation dynamique sert quand un problème se découpe en sous-problèmes qui se répètent. L’idée tient en une phrase : on calcule chaque sous-problème une seule fois et on mémorise son résultat pour le réutiliser.
1️⃣ Le problème : des calculs répétés
On reprend la suite de Fibonacci du sujet de Polynésie 2026 : \( U_0 = 0 \), \( U_1 = 1 \) et \( U_n = U_{n-1} + U_{n-2} \). La version récursive suit directement cette définition :
def suite(n):
if n < 2:
return n
return suite(n - 1) + suite(n - 2)
Elle est juste, mais très lente : pour calculer suite(5), elle calcule suite(3)
deux fois, suite(2) trois fois… Le nombre d’additions croît exponentiellement avec n.
2️⃣ La solution : mémoriser
Méthode descendante : la mémoïsation
On garde la fonction récursive, mais on stocke chaque résultat dans un dictionnaire. Avant de calculer, on regarde s’il est déjà connu.
memo = {}
def suite2(n):
if n < 2:
return n
if n not in memo:
memo[n] = suite2(n - 1) + suite2(n - 2)
return memo[n]
Méthode ascendante : un tableau
On part des plus petits cas et on remplit un tableau jusqu’à n : chaque case utilise les cases déjà remplies. Plus de récursivité.
def suite3(n):
if n < 2:
return n
U = [0] * (n + 1)
U[1] = 1
for i in range(2, n + 1):
U[i] = U[i - 1] + U[i - 2]
return U[n]
Avec l’une ou l’autre méthode, chaque terme de \( U_2 \) à \( U_n \) est calculé une seule fois : il n’y a plus que n − 1 additions (6 pour n = 7, contre 20 pour la version récursive simple).
3️⃣ Le coût en mémoire
On gagne du temps en utilisant de la mémoire pour stocker les résultats. Ici, on peut même s’en passer : pour calculer \( U_i \), seules les deux dernières valeurs servent.
def suite4(n):
a, b = 0, 1 # U(0) et U(1)
for i in range(n):
a, b = b, a + b # on avance d’un cran
return a
| Version | Additions pour \( U_n \) | Mémoire utilisée |
|---|---|---|
| récursive simple | exponentiel (20 pour n = 7) | la pile des appels (n niveaux) |
| mémoïsation | n − 1 | le dictionnaire + la pile des appels |
| tableau (ascendante) | n − 1 | un tableau de n + 1 cases |
| deux variables | n − 1 | constante (deux nombres) |
La version itérative est préférable : pas d’appels récursifs (Python limite leur nombre à environ 1000) et une mémoire minimale.
4️⃣ Un autre exemple : le rendu de monnaie
On veut rendre une somme avec le moins de pièces possible. Avec les pièces 1, 3 et 4, l’algorithme glouton (prendre toujours la plus grosse pièce possible) rend 6 = 4 + 1 + 1, soit 3 pièces, alors que 6 = 3 + 3 n’en utilise que 2.
Relation de récurrence : si nb[s] est le nombre minimal de pièces pour rendre s, on essaie chaque
pièce p en premier : nb[s] = 1 + min(nb[s - p]) pour les pièces p ≤ s, avec
nb[0] = 0.
def rendu(somme, pieces):
nb = [0] * (somme + 1) # nb[s] : minimum de pièces pour s
for s in range(1, somme + 1):
nb[s] = s # au pire, s pièces de 1
for p in pieces:
if p <= s and nb[s - p] + 1 < nb[s]:
nb[s] = nb[s - p] + 1
return nb[somme]
rendu(6, [1, 3, 4]) # 2
Autre exemple classique, cité par le programme : l’alignement de séquences (comparer deux mots ou deux brins d’ADN), qui se résout aussi en remplissant un tableau case par case.