La programmation dynamique en prépa
La programmation dynamique est souvent le « plafond de verre » des étudiants en prépa (MP2I, MPI, Info optionnelle).
La difficulté n’est pas syntaxique, mais conceptuelle :
Le saut d’abstraction : Contrairement aux algorithmes « gloutons » qui choisissent la meilleure option immédiate, la programmation dynamique impose de voir le problème comme une imbrication de sous-problèmes. Identifier cette sous-structure optimale est un défi logique pur.
La récurrence : C’est le point de rupture. Il faut définir un état et une transition mathématique exacte. Une erreur d’indice ou une condition initiale mal définie, et tout l’édifice s’écroule.
L’efficacité spatiale : En concours (X/ENS, Mines), trouver la solution ne suffit pas. On attend souvent une optimisation de la mémoire, ce qui ajoute une couche de complexité technique à une logique déjà dense.
Le cours magistral donne la solution ; le cours particulier donne la méthode de recherche.
Apprendre à « penser programmation dynamique » : Un tuteur ne donne pas la réponse. Il pose les questions clés : « Quel est le dernier choix fait pour arriver ici ? » ou « De quoi as-tu besoin pour calculer l’étape ? ».
Coder ensemble : En ligne, le partage d’écran permet de coder ensemble temps réel. Rédiger les commentaires à deux.
Cibler les classiques de concours : Le sac à dos, le rendu de monnaie, les coefficients binomiaux, ou l’alignement de séquences sont des « patterns ». Le rythme obtenu grâce au duo permet la multiplication d’exemples qui illustrent ces « patterns ».
- La progressivité des exemples et la validation : c’est la clé pour apprendre vite et bien avec des bases solides et des points de référence.
C’est en particulier ce dernier point qui fait tout l’intérêt du cours particulier en informatique.