La programmation dynamique (DP) résout les problèmes avec des sous-problèmes qui se chevauchent et une structure optimale en calculant chaque sous-problème une seule fois et en réutilisant le résultat. Les deux styles sont la mémoïsation (top-down) et la tabulation (bottom-up).
La récursion naïve recalcule les mêmes sous-problèmes de façon exponentielle. La DP les met en cache, réduisant le travail exponentiel à polynomial.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Mémoïsation | Tabulation | |
|---|---|---|
| Direction | récursion top-down | itération bottom-up |
| Calcule | uniquement les états nécessaires | tous les états |
| Risque | débordement de pile | aucun |
| Espace | peut être réduit | souvent réductible à O(1) lignes |
Fibonacci : de O(2ⁿ) naïf à O(n) en temps, O(n) (ou O(1)) en espace.
Utilisez la DP quand les sous-problèmes se chevauchent. Définissez l'état et la récurrence avec soin — c'est la partie difficile. Si les sous-problèmes ne se chevauchent pas, une simple divide-and-conquer suffit.
La DP convertit les problèmes exponentiels insolubles — chemins les plus courts, distance d'édition, knapsack — en problèmes efficients.
La capacité à identifier l'état et la récurrence est l'une des plus recherchées dans les entretiens d'algorithmes.
Elle sous-tend les systèmes réels, des outils diff à l'alignement de séquences en bioinformatique.