Comment fonctionne la programmation dynamique en NSI
La programmation dynamique est une technique algorithmique puissante au programme de terminale NSI. Elle résout des problèmes d'optimisation en décomposant un problème en sous-problèmes chevauchants et en mémorisant leurs solutions pour éviter de les recalculer. Le principe repose sur deux idées : la sous-structure optimale (la solution optimale contient des solutions optimales de sous-problèmes) et le chevauchement des sous-problèmes (les mêmes sous-problèmes apparaissent plusieurs fois). L'exemple classique est la suite de Fibonacci : la version récursive naïve a une complexité O(2^n) car elle recalcule les mêmes valeurs. Avec la mémoïsation (stocker les résultats dans un dictionnaire), la complexité tombe à O(n). Le problème du rendu de monnaie est un autre exemple fondamental : trouver le nombre minimal de pièces pour rendre une somme donnée. La version gloutonne ne donne pas toujours la solution optimale, mais la programmation dynamique oui. L'approche peut être descendante (récursivité + mémoïsation) ou ascendante (remplissage d'un tableau itérativement). Sur NSI-Lycée, chaque problème de programmation dynamique est illustré avec des tableaux de remplissage animés et du code Python commenté. Consultez revisemaths.fr pour les raisonnements par récurrence, et alloexercices.fr pour des exercices d'algorithmique avancée.
