Programmation dynamique : fiche de révision de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
La programmation dynamique traite un problème d'optimisation en le coupant en sous-problèmes, réglés du plus petit au plus grand, dont on garde les résultats6.
Trois temps : définir les sous-problèmes, écrire la relation de récurrence, choisir une méthode ascendante ou descendante6.
Elle sert quand les mêmes sous-problèmes reviennent plusieurs fois, là où diviser pour régner devient inefficace 6.
Piège classique : oublier les cas de base ou recalculer sans mémoriser, ce qui fait exploser le temps de calcul.
L'idée à retenir
Pourquoi mémoriser ? Le lien avec diviser pour régner
Tu connais diviser pour régner, comme le tri fusion : on sépare le problème en sous-problèmes indépendants, on les résout par récursivité, puis on fusionne les résultats 6. Cette méthode perd son efficacité dès qu'un même sous-problème est à résoudre plusieurs fois 6.
La programmation dynamique corrige ce défaut : chaque sous-problème est résolu une seule fois, son résultat est rangé dans un tableau ou un dictionnaire, puis réutilisé. La mémoïsation est une technique très voisine, fondée sur la même idée : ne pas refaire un calcul déjà fait 5.
Méthode : concevoir un algorithme
Deuxième exemple : le rendu de monnaie
On cherche le nombre minimal de pièces pour atteindre une somme donnée avec des valeurs faciales données. Une formulation récursive teste chaque pièce x et garde le minimum de 1+ (solution pour la somme moins x) 2.
Où la rencontre-t-on, et quels pièges éviter
Le problème du sac à dos est un problème classique de recherche opérationnelle, NP-difficile, mais résolu de façon pseudo-polynomiale par programmation dynamique 6. Dans son énoncé, on dispose de n objets ayant chacun un poids et une valeur 4. La recherche de la plus longue sous-chaîne commune à deux textes se traite aussi ainsi 2, et le travail sur les indices y est délicat 2.
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Les appels récursifs se recoupent : F3 est recalculé plusieurs fois dans le calcul de F56. Le cas de base existe bien (F0 et F1), donc l'erreur n'est pas là, et aucun tri n'intervient.
Le paradigme repose sur la définition de sous-problèmes puis sur une relation de récurrence 6. Découper en moitiés indépendantes caractérise diviser pour régner, pas la programmation dynamique.
C'est faux : diviser pour régner suffit pour des sous-problèmes indépendants, et il devient inefficace quand un même sous-problème revient plusieurs fois 6. C'est précisément ce cas que la mémorisation traite.
V[6]=1+min(V[5],V[3],V[2])=1+min(2,1,2)=2 : deux pièces de 3. La réponse 3, tentante, vient du choix glouton 4 + 1 + 1, qui n'est pas optimal.
Les questions qu'on se pose
Quelle est la différence entre programmation dynamique et mémoïsation ?
Ce sont deux techniques très proches, fondées sur l'idée de ne pas refaire un calcul déjà effectué 5. La mémoïsation est la version descendante : on garde en mémoire les résultats d'une fonction récursive. La version ascendante remplit un tableau en partant des plus petits sous-problèmes.
Comment savoir si un problème se traite par programmation dynamique ?
Cherche d'abord un problème d'optimisation 6, puis vérifie deux choses : une solution optimale se construit à partir de solutions optimales de sous-problèmes 6, et ces sous-problèmes se répètent. Si tu parviens à écrire une relation de récurrence avec des cas de base, c'est bon signe.
Faut-il toujours préférer la programmation dynamique à la récursion simple ?
Non. Si les sous-problèmes sont indépendants, comme dans un tri fusion, la récursion simple suffit 6. La programmation dynamique apporte un gain quand les mêmes sous-problèmes reviennent, au prix de la mémoire utilisée pour les stocker.