Programmation dynamique

La programmation dynamique permet d’optimiser certains problèmes complèxes en conservant le résultats de sous calculs en mémoire afin de gagner du temps dans la résolution globale de celui-ci.

Dans le problème du sac à dos par exemple lorsqu’on teste toutes les combinaisons possibles, la plupart de celles-ci reviendront à de nombreuses reprises et il est profitable de ne pas à avoir à les recalculer à chaque reprise. De la sorte on peut utiliser la mémoire pour garder en cache le résultat de calculs antérieurs.

La programmation dynamique ne s’applique pas aux problèmes de type divide and conquer tels que la recherche dichotomique, mais plutot aux problèmes NP-complets jusqu’à un certain ordre de grandeur.

Il permet dans tous les cas de gagner au moins un ordre de grandeur dans la plupart des problèmes NP-complets et il est généralement avantageux de l’utiliser en programmation compétitive . Autrement dit un algorithme non polynomial exhaustif qui s’exécute en quelques minutes pour un problème donné peut s’exécuter en quelques secondes si on lui ajout une couche dynamique, un algorithme qui s’exécute en quelques secondes peut s’exécuter avec une couche dynamique supplémentaire en une fraction de seconde, etc.