Publié · en amélioration
Algorithm
La programmation dynamique mémorise et réutilise les solutions de sous-problèmes qui se chevauchent, et remplace des recherches exponentielles par des tables.
La programmation dynamique (DP) est une technique de conception d'algorithmes qui découpe un problème en sous-problèmes plus petits, résout chacun une seule fois, enregistre la réponse et la réutilise dès que le même sous-problème réapparaît. Formalisée par Richard Bellman dans les années 1950, elle s'applique lorsque les sous-problèmes se chevauchent et qu'une solution optimale se construit à partir des solutions optimales de ses sous-problèmes.
Beaucoup de problèmes qui demandent un temps exponentiel avec une récursion naïve ou une recherche exhaustive se résolvent en un temps proportionnel au nombre d'états. La programmation dynamique est au cœur des outils diff, de la distance d'édition des correcteurs orthographiques, de l'alignement de séquences d'ADN, de l'algorithme de Viterbi en reconnaissance vocale et du choix de l'ordre des jointures dans les optimiseurs de bases de données. C'est aussi l'un des sujets les plus fréquents en entretien technique.
Commencez par Fibonacci pour comprendre la différence entre mémoïsation (descendante) et tabulation (ascendante), puis traitez les grands classiques : rendu de monnaie, sac à dos 0/1, plus longue sous-suite croissante, plus longue sous-séquence commune et distance d'édition. Pour chaque problème, écrivez d'abord l'état, la relation de récurrence, les cas de base et l'ordre de calcul, vérifiez la récurrence en remplissant une petite table à la main, puis seulement écrivez le code.
Lorsqu'un même sous-problème revient souvent, il est calculé une seule fois et stocké : le travail répété devient une simple lecture de table.
Une solution optimale doit pouvoir se construire à partir de solutions optimales des sous-problèmes ; c'est ce qui justifie la récurrence.
On l'implémente de façon descendante en ajoutant un cache à la récursion (functools.cache) ou ascendante en remplissant une table avec des boucles.
L'état ne contient que les paramètres qui déterminent la réponse, et des tableaux glissants ne gardent en mémoire que les lignes utiles.
knapsack résout le problème du sac à dos 0/1 de façon ascendante avec une seule ligne, en parcourant les capacités de la plus grande à la plus petite pour que chaque objet soit pris au plus une fois. lcs calcule la longueur de la plus longue sous-séquence commune de façon descendante, mémoïsée avec functools.cache. La commande python dynamic_programming.py affiche 9 et 4.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySix chapitres pour aller de l'installation aux notions essentielles de Programmation dynamique.
Posez vos questions, partagez votre expérience et échangez vos avis sur Programmation dynamique.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.