Tu as déjà croisé la programmation dynamique en cours de NSI, et tu as peut-être eu l'impression de te noyer dans les tableaux et les boucles imbriquées ? Rassure-toi : c'est une notion exigeante, mais redoutablement efficace une fois comprise. Le problème, c'est que même les élèves sérieux tombent dans des pièges classiques qui coûtent des points le jour du bac. Dans cet article, on va décortiquer ensemble les erreurs les plus fréquentes, avec du code Python commenté et des exemples concrets. À la fin, tu sauras repérer ces pièges et les éviter.
1. Qu'est-ce que la programmation dynamique, vraiment ?
La programmation dynamique NSI est une méthode de résolution de problèmes qui consiste à découper un problème complexe en sous-problèmes plus simples, à mémoriser les résultats de ces sous-problèmes pour ne pas les recalculer, puis à combiner ces résultats pour obtenir la solution finale. Elle repose sur deux propriétés clés :
- La sous-structure optimale : la solution optimale du problème global se construit à partir des solutions optimales de sous-problèmes.
- Les sous-problèmes qui se chevauchent : les mêmes sous-problèmes reviennent plusieurs fois. C'est là que la mémorisation (mémoïsation ou tabulation) fait gagner un temps fou.
Attention à ne pas confondre avec la récursivité simple ou avec l'approche gloutonne (greedy). La programmation dynamique garantit souvent l'optimalité là où un algorithme glouton peut échouer. C'est une distinction que les correcteurs adorent tester.
Les deux grandes familles d'implémentation
On distingue deux approches :
- Top-down (mémoïsation) : on écrit une fonction récursive et on stocke les résultats déjà calculés dans un dictionnaire ou une liste.
- Bottom-up (tabulation) : on remplit un tableau itérativement, du plus petit sous-probl��me vers le plus grand.
Les deux sont valides au bac, mais la version bottom-up est souvent plus simple à analyser en complexité. Le piège numéro un ? Utiliser la récursivité sans mémoïsation et se retrouver avec une complexité exponentielle.
2. Les pièges classiques (et comment les éviter)
Piège n°1 : oublier la mémoïsation
C'est l'erreur la plus fréquente. Tu écris une jolie fonction récursive pour Fibonacci, tu la testes sur fib(10), ça marche. Mais sur fib(50), ton programme met une éternité. Pourquoi ? Parce que sans mémoïsation, tu recalculés les mêmes valeurs des milliers de fois.
# Version naïve : complexité exponentielle O(2^n)
def fib_naif(n):
if n <= 1:
return n
return fib_naif(n-1) + fib_naif(n-2)
# Version mémoïsée : complexité linéaire O(n)
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
Retiens bien : si tu vois une récursion avec des appels répétés sur les mêmes paramètres, pense mémoïsation. C'est le réflexe à avoir.
Piège n°2 : mal définir l'état
En programmation dynamique, tout repose sur la définition de l'état : que représente exactement dp[i] ou dp[i][j] ? Si ta définition est floue, ton algorithme sera faux. Par exemple, pour le sac à dos (knapsack), dp[i][w] doit représenter la valeur maximale qu'on peut obtenir avec les i premiers objets et une capacité w. Si tu te trompes d'un indice, tout s'écroule.
Astuce : écris en commentaire la signification de chaque case de ton tableau avant de coder. Ça t'évite 80 % des bugs.
Piège n°3 : erreurs d'indices et de bornes
Les tableaux en Python commencent à l'indice 0, mais beaucoup de formulations mathématiques commencent à 1. Résultat : des IndexError ou des résultats décalés. Prends l'habitude de dimensionner tes tableaux avec une case supplémentaire si nécessaire, et de vérifier tes bornes de boucles.
# Sac à dos : attention aux indices
n = len(objets)
dp = [[0] * (capacite + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacite + 1):
if poids[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-poids[i-1]] + valeurs[i-1])
else:
dp[i][w] = dp[i-1][w]
Note bien le i-1 pour accéder aux objets, et le n+1 pour la taille du tableau. C'est ce genre de détail qui fait la différence.
Piège n°4 : confondre programmation dynamique et diviser pour régner
Diviser pour régner (comme le tri fusion) découpe le problème en sous-problèmes indépendants. La programmation dynamique, elle, traite des sous-problèmes qui se chevauchent. Si tu appliques la mauvaise méthode, tu perds soit en performance, soit en correction. Le tri fusion n'a pas besoin de mémoïsation ; Fibonacci, si.
3. Cas d'usage concret : le rendu de monnaie
Imaginons que tu doives rendre une somme avec le minimum de pièces, sachant que tu disposes de pièces de 1, 3 et 4 unités. Un algorithme glouton (prendre toujours la plus grosse pièce possible) échoue ici : pour 6, il donnerait 4+1+1 (3 pièces) alors que 3+3 (2 pièces) est optimal. La programmation dynamique, elle, trouve la bonne réponse.
def rendu_monnaie(somme, pieces):
# dp[s] = nombre minimal de pièces pour faire la somme s
dp = [float('inf')] * (somme + 1)
dp[0] = 0
for s in range(1, somme + 1):
for p in pieces:
if p <= s:
dp[s] = min(dp[s], dp[s-p] + 1)
return dp[somme]
print(rendu_monnaie(6, [1, 3, 4])) # Affiche 2
Ici, l'état dp[s] est clair : nombre minimal de pièces pour atteindre la somme s. On remplit le tableau de proche en proche. La complexité est en O(somme × nombre de pièces), ce qui est très raisonnable.
Ce type d'exercice tombe régulièrement au bac. Pour t'entraîner, tu peux consulter nos exercices corrigés de NSI qui couvrent ce chapitre.
4. Méthode de révision et lien avec l'épreuve du bac
La programmation dynamique figure explicitement au programme de Terminale NSI, dans le thème « Algorithmique ». À l'écrit comme à l'oral, on peut te demander :
- D'écrire une fonction récursive avec mémoïsation.
- De compléter un tableau de programmation dynamique.
- D'analyser la complexité d'un algorithme.
- De comparer avec une approche gloutonne.
Voici une méthode de révision en 4 étapes :
- Maîtrise les classiques : Fibonacci, sac à dos, rendu de monnaie, plus longue sous-séquence commune (LCS). Ce sont les exemples les plus fréquents.
- Entraîne-toi à définir l'état avant de coder. Écris toujours un commentaire du type
# dp[i] = .... - Vérifie tes bornes : fais tourner ton code à la main sur un petit exemple (n=3 ou 4).
- Analyse la complexité : sais-tu dire si ton algorithme est en O(n), O(n²) ou O(2^n) ? C'est une question quasi systématique.
Pour approfondir, jette un œil à nos cours de NSI et à nos fiches de révision. Et si tu veux travailler avec un prof particulier, le réseau AlloLycée propose des cours adaptés au programme officiel. Pour les élèves de collège qui préparent le brevet 2026, AlloBac couvre aussi les bases de l'algorithmique.
Même si la programmation dynamique n'est pas explicitement au programme de 3ème, les notions de boucles et de variables que tu y apprends te serviront de socle pour la révision 3ème et pour aborder sereinement le lycée. Un bon réflexe : commence par des exercices simples de calcul de suites avant de te lancer dans les tableaux à deux dimensions.
5. Conclusion : la programmation dynamique, un investissement rentable
La programmation dynamique peut sembler intimidante, mais une fois que tu as compris les deux ou trois réflexes clés — définir l'état, mémoïser, vérifier les bornes — elle devient un outil puissant et très valorisé au bac. Ne te décourage pas si tu fais des erreurs au début : c'est en les corrigeant que tu progresses. Prends le temps de coder chaque exemple à la main, de le tester, de le modifier. Et n'oublie pas : un algorithme correct mais lent peut être optimisé, alors qu'un algorithme faux ne vaut rien.
Tu as maintenant toutes les cartes en main pour éviter les pièges classiques. Alors, à toi de jouer : ouvre ton éditeur Python, reprends l'exemple du rendu de monnaie, et essaie de le modifier pour afficher aussi la liste des pièces utilisées. Bon courage, tu vas y arriver !
