Programmation dynamique — mémoïsation et tabulation expliquées

La programmation dynamique est une manière de résoudre des problèmes en enregistrant les réponses à de plus petits sous-problèmes pour les réutiliser ensuite. Elle est utile quand les mêmes sous-problèmes réapparaissent et que la réponse complète peut être construite à partir de ces réponses plus petites.

Les deux grandes approches sont la mémoïsation et la tabulation. La mémoïsation stocke les réponses pendant une solution récursive. La tabulation remplit les réponses de bas en haut, généralement avec un tableau ou une table.

Quand la programmation dynamique fonctionne

La programmation dynamique est utile lorsque deux conditions sont réunies.

D’abord, les sous-problèmes se recouvrent. Cela signifie que le même résultat intermédiaire est nécessaire plus d’une fois. Ensuite, les réponses plus grandes peuvent être construites à partir de réponses plus petites de manière cohérente.

Si ces conditions ne sont pas réunies, stocker d’anciens résultats peut ajouter un coût mémoire sans apporter beaucoup d’aide.

Mémoïsation vs tabulation

Mémoïsation : stockage de haut en bas

La mémoïsation part de l’idée récursive. Quand l’algorithme résout un sous-problème pour la première fois, il stocke le résultat. Les appels suivants réutilisent la valeur enregistrée au lieu de la recalculer.

Cette approche est souvent plus simple quand la récurrence est claire, mais que l’ordre de tous les états nécessaires ne l’est pas.

Tabulation : construction de bas en haut

La tabulation part des cas de base et remplit les états dans un ordre qui rend les dépendances disponibles au moment voulu.

Cette approche est souvent plus simple quand vous connaissez déjà un ordre d’itération clair et que vous voulez un contrôle explicite sur la table.

Exemple de programmation dynamique : Fibonacci

La suite de Fibonacci est définie par

$$F(0) = 0, \quad F(1) = 1$$

et, pour $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Une solution récursive simple répète des calculs. Par exemple, calculer $F(5)$ nécessite $F(4)$ et $F(3)$, puis calculer $F(4)$ nécessite encore $F(3)$. Cet appel répété à $F(3)$ est exactement le type de gaspillage que la programmation dynamique élimine.

Mémoïsation sur Fibonacci

Avec la mémoïsation, la récurrence reste la même, mais chaque valeur est stockée après son premier calcul.

Pour $F(5)$, la suite utile est :

• calculer et stocker $F(0)=0$
• calculer et stocker $F(1)=1$
• calculer et stocker $F(2)=1$
• calculer et stocker $F(3)=2$
• calculer et stocker $F(4)=3$
• calculer et stocker $F(5)=5$

Le point essentiel est que chaque état n’est calculé qu’une seule fois. Les demandes suivantes lisent la valeur stockée.

Tabulation sur Fibonacci

Avec la tabulation, on construit à partir des cas de base :

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Cette version rend l’ordre des dépendances évident : chaque nouvelle valeur utilise des entrées déjà connues.

Pourquoi la programmation dynamique peut être plus rapide

Si un problème n’a que $k$ états distincts importants, la programmation dynamique essaie de résoudre chacun de ces $k$ états une seule fois. Cela peut transformer un grand arbre récursif en un calcul beaucoup plus petit.

Le gain exact dépend du problème. La programmation dynamique n’est pas automatiquement rapide. Elle aide quand les calculs répétés constituent réellement une part importante de la solution d’origine.

Erreurs fréquentes en programmation dynamique

L’utiliser quand les sous-problèmes ne se recouvrent pas

Tous les problèmes récursifs ne sont pas des problèmes de programmation dynamique. Si presque tous les sous-problèmes sont différents, mettre les résultats en cache peut ne pas économiser assez de travail pour faire une vraie différence.

Définir le mauvais état

L’état doit contenir toutes les informations nécessaires pour l’étape suivante. S’il manque une information importante, la récurrence peut sembler correcte tout en produisant de mauvaises réponses.

Se tromper dans les cas de base

Les cas de base servent de point d’ancrage à toute la méthode. Si les valeurs de départ sont fausses, tous les états construits ensuite à partir d’elles seront faux aussi.

Remplir la table dans le mauvais ordre

La tabulation ne fonctionne que si chaque état est rempli après les états dont il dépend. Une récurrence correcte peut quand même échouer si l’ordre de remplissage est mauvais.

Supposer que la programmation dynamique signifie toujours optimisation

Beaucoup d’exemples célèbres cherchent à maximiser ou minimiser quelque chose, mais la programmation dynamique sert aussi pour des problèmes de comptage et de décision. Le vrai signal, ce sont les sous-problèmes réutilisables, pas le mot « meilleur ».

Où la programmation dynamique est utilisée

La programmation dynamique apparaît dans des problèmes comme la distance d’édition, la plus longue sous-séquence commune, le comptage de chemins, l’optimisation de type sac à dos et certains contextes de plus court chemin.

Quand vous vous demandez si vous devez l’essayer, posez-vous deux questions :

• les petits sous-problèmes se répètent-ils ?
• la réponse plus grande peut-elle être construite à partir de ces réponses plus petites ?

Si la réponse est oui dans les deux cas, la programmation dynamique est une très bonne candidate.

Essayez un problème similaire

Essayez votre propre version avec le nombre de façons de monter $n$ marches si chaque déplacement est soit de $1$ marche, soit de $2$ marches. La récurrence est simple, les sous-problèmes répétés sont faciles à repérer, et c’est un très bon exemple après Fibonacci.