La programmation dynamique est une technique d’algorithmique qui consiste à résoudre un problème en réutilisant les résultats de sous-problèmes déjà calculés. En Python, elle se traduit souvent par deux approches : la mémoïsation avec un cache, ou la tabulation avec un tableau rempli progressivement.
Elle est utile dès qu’un problème présente deux propriétés : des sous-problèmes qui se répètent, et une solution globale qui dépend de solutions plus petites. Fibonacci, les chemins dans une grille, le sac à dos, les coefficients binomiaux ou certains jeux à deux joueurs sont de bons exemples.
La réponse courte
La programmation dynamique en Python suit toujours la même logique :
- définir l’état du problème ;
- écrire la transition entre un état et les états plus petits ;
- choisir une condition de départ ;
- mémoriser les résultats pour éviter les recalculs ;
- vérifier la complexité obtenue.
Version mémoïsée de Fibonacci :
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(40))
La version récursive naïve recalcule les mêmes valeurs de nombreuses fois. Avec lru_cache, chaque fibonacci(k) est calculé une seule fois.
Mémoïsation ou tabulation
La mémoïsation part souvent d’une fonction récursive. On écrit la solution naturelle, puis on ajoute un cache.
La tabulation part de la base. On remplit un tableau dans l’ordre nécessaire, jusqu’à obtenir la réponse finale.
| Approche | Idée | Avantage | Limite |
|---|---|---|---|
| Mémoïsation | récursion + cache | très lisible quand la relation est naturelle | attention à la profondeur de récursion |
| Tabulation | tableau rempli progressivement | contrôle clair de l’ordre et de la mémoire | demande parfois plus de réflexion au départ |
Version tabulée de Fibonacci :
def fibonacci_iteratif(n):
if n < 2:
return n
precedent = 0
courant = 1
for _ in range(2, n + 1):
precedent, courant = courant, precedent + courant
return courant
print(fibonacci_iteratif(40))
Cette version est en O(n) en temps et O(1) en mémoire. Elle est souvent préférable en production pour ce problème précis.
Exemple : compter les chemins dans une grille
Supposons une grille de lignes x colonnes. On part en haut à gauche et on veut arriver en bas à droite. À chaque étape, on peut seulement aller vers la droite ou vers le bas.
Le nombre de chemins jusqu’à une case est la somme des chemins venant de la case du haut et de la case de gauche.
def compter_chemins(lignes, colonnes):
dp = [[0] * colonnes for _ in range(lignes)]
for ligne in range(lignes):
dp[ligne][0] = 1
for colonne in range(colonnes):
dp[0][colonne] = 1
for ligne in range(1, lignes):
for colonne in range(1, colonnes):
dp[ligne][colonne] = dp[ligne - 1][colonne] + dp[ligne][colonne - 1]
return dp[-1][-1]
print(compter_chemins(3, 4))
Ici, l’état est dp[ligne][colonne]. La transition est :
dp[ligne][colonne] = dp[ligne - 1][colonne] + dp[ligne][colonne - 1]
La complexité est O(lignes * colonnes).
Exemple : le sac à dos 0/1
Le problème du sac à dos illustre bien l’intérêt de la programmation dynamique. On a des objets, chacun avec un poids et une valeur. On veut maximiser la valeur totale sans dépasser une capacité.
Dans la version 0/1, chaque objet est pris ou ignoré.
def sac_a_dos(objets, capacite):
dp = [0] * (capacite + 1)
for poids, valeur in objets:
for c in range(capacite, poids - 1, -1):
dp = max(dp, dp + valeur)
return dp[capacite]
objets = [(2, 3), (3, 4), (4, 5), (5, 8)]
print(sac_a_dos(objets, 8))
La boucle sur les capacités se fait à l’envers pour éviter de réutiliser plusieurs fois le même objet dans la même étape. C’est une erreur fréquente : si vous parcourez dans le mauvais sens, vous résolvez sans le vouloir une autre variante du problème.
Comment reconnaître un problème de programmation dynamique
Un problème est un bon candidat si vous voyez ces signaux :
- une solution récursive évidente, mais trop lente ;
- des sous-problèmes identiques qui reviennent ;
- une phrase comme “meilleur résultat jusqu’à cette position” ;
- une grille, une séquence, un préfixe, une capacité ou un score ;
- une décision répétée : prendre ou ne pas prendre, avancer ou rester, choisir un coup.
Exemples :
| Problème | État possible |
|---|---|
| Fibonacci | n |
| Chemins dans une grille | (ligne, colonne) |
| Sac à dos | (index_objet, capacite_restante) |
| Coefficients binomiaux | (n, k) |
| Distance d’édition | (i, j) |
| Jeu à deux joueurs | (position, joueur, profondeur) |
Pour les coefficients binomiaux, vous pouvez lire aussi le guide math.comb et triangle de Pascal.
Les erreurs fréquentes
La première erreur est de choisir un état trop large. Si votre clé de cache contient toute une liste alors qu’un simple index suffit, le programme devient lourd.
La deuxième erreur est d’oublier les conditions de départ. Une transition correcte ne sert à rien si les premières cases du tableau sont mal initialisées.
La troisième erreur est de confondre récursion et programmation dynamique. Une fonction récursive sans cache peut rester exponentielle.
La quatrième erreur est de ne pas mesurer la mémoire. Certains tableaux DP en deux dimensions peuvent être réduits en une seule dimension.
La cinquième erreur est de vouloir utiliser la programmation dynamique partout. Si un problème n’a pas de sous-problèmes qui se répètent, un algorithme glouton, un tri ou une structure comme heapq peut être plus simple.
Où placer cette notion dans votre apprentissage
La programmation dynamique arrive après la complexité, les structures de données, les tris et les graphes de base. Elle demande de raisonner sur l’état, pas seulement d’écrire une boucle.
Pour continuer dans le bon ordre :
- Algorithmes Python : tous les guides pour apprendre pas à pas
- Complexité algorithmique en Python
- Minimax en Python
- Negamax en Python
La règle à retenir : définissez l’état, écrivez la transition, posez les cas de base, puis seulement ensuite codez. Si ces quatre éléments sont clairs, la programmation dynamique devient beaucoup moins mystérieuse.
Références
- Documentation Python – functools.lru_cache
- Documentation Python – functools.cache
- Documentation Python – math.comb
- Documentation Python – sys.setrecursionlimit
