"Ceux qui ne se souviennent pas du passé sont condamnés à le répéter", Programmation Dynamique

La Programmation Dynamique est une méthode pour résoudre un problème complexe en le décomposant en une collection de sous-problèmes plus simples, en résolvant chacun de ces sous-problèmes une seule fois et en stockant leurs solutions en utilisant une structure de données basée sur la mémoire (tableau, carte, etc.).

Chacune des solutions de sous-problème est indexée d'une manière ou d'une autre, généralement en fonction des valeurs de ses paramètres d'entrée, afin de faciliter sa recherche. Ainsi, la prochaine fois que le même sous-problème se produit, au lieu de recalculer sa solution, on recherche simplement la solution précédemment calculée, économisant ainsi du temps de calcul.

Par exemple, la création d'arbres phylogénétiques une fois que l'ADN est connu peut être abordée facilement avec la programmation dynamique:

Cliquez ici pour une liste complète des problèmes pouvant être résolus avec la programmation dynamique.