À retenir
- Elle évite de refaire le même travail plusieurs fois.
- Elle repose sur le stockage des solutions (mémoïsation ou tabulation).
- Elle transforme souvent un temps d'exécution exponentiel (très lent) en temps linéaire ou polynomial (rapide).
La programmation dynamique est une méthode qui permet de résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples, puis en enregistrant les résultats de ces derniers pour ne pas avoir à les recalculer. C'est un peu comme si, lors d'un long calcul, vous notiez les étapes intermédiaires sur un brouillon pour pouvoir les réutiliser instantanément si elles se présentent à nouveau.
Étymologie
Le concept a été formalisé par Richard Bellman dans les années 1950. À cette époque, le mot programmation ne désignait pas l'écriture de code informatique, mais la planification ou l'ordonnancement de tâches. Bellman a choisi l'adjectif dynamique pour souligner l'aspect temporel et évolutif de la méthode, mais aussi parce qu'il trouvait que cela sonnait bien auprès de ses financeurs.
Exemples d'usage
- La suite de Fibonacci : au lieu de recalculer chaque nombre en repartant de zéro, on additionne les deux derniers résultats stockés en mémoire.
- Le problème du rendu de monnaie : trouver le nombre minimal de pièces pour faire l'appoint en se basant sur les combinaisons déjà testées.
- L'alignement de séquences ADN : comparer deux brins de code génétique en cherchant les segments communs les plus longs.
Cas d'usage
On l'utilise massivement en optimisation (trouver le chemin le plus court ou le coût le plus bas), en bio-informatique, en traitement du langage naturel (reconnaissance vocale) et en finance pour la gestion de portefeuilles.
Bonnes pratiques
Pour appliquer cette méthode, vérifiez que votre problème présente des sous-problèmes chevauchants (les mêmes calculs reviennent souvent). Soyez attentifs à la consommation de mémoire : stocker tous les résultats intermédiaires peut s'avérer coûteux si le problème est gigantesque.
Synonymes
Antonymes
Conseil
Si vous débutez, essayez d'abord de résoudre un problème par récursivité simple. Si vous voyez que votre fonction est appelée plusieurs fois avec les mêmes paramètres, c'est le signal parfait pour passer à la programmation dynamique.
Questions fréquentes
Quelle est la différence avec l'approche 'Diviser pour régner' ?
Le 'Diviser pour régner' sépare le problème en morceaux indépendants (comme le tri fusion), alors que la programmation dynamique gère des morceaux qui se recoupent et se répètent.
Est-ce que cela consomme beaucoup de RAM ?
Oui, car on échange de la mémoire (pour stocker les résultats) contre du temps de calcul (pour aller plus vite).