C16.2 : Programmation dynamique

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre le sous-problème et ainsi de suite, tout en stockant les résultats intermédiaires s'ils sont susceptibles d'être utilisés plusieurs fois.

La programmation dynamique donne une réponse exacte au problème posé.

Dans la méthode ascendante (bottom-up), on commence par traiter le sous-problème le plus petit, on avance de proche en proche.

Dans la méthode descendante (top-down), on raisonne récursivement (en commençant par le cas général).

Le stockage des résultats intermédiaires s'appelle la mémoïsation.