Programmation dynamique
Les fonctions à mémoire
S'affranchir de calculs inutiles
Tout comme la méthode diviser & régner calcule des valeurs plusieurs fois, la programmation dynamique peut calculer elle aussi des valeurs inutiles. En effet, on faisant les calculs de bas en haut, on est amené à calculer des valeurs qui peuvent ne pas être utilisées par la suite.
La technique de la fonction mémoire permet de combiner le principe simple et élégant de la méthode diviser & régner — la récursivité — avec l’efficacité de la programmation dynamique. L’idée de ce type de fonction est donc est d’utiliser un tableau des solutions aux sous-problèmes avec la fonction récursive exprimant la résolution du problème original.