Numérique et sciences informatiques (spécialité) · TerminaleBac

Programmation dynamique : exercices corrigés de Terminale NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

La programmation dynamique découpe un problème en sous-problèmes, traite d'abord les plus petits puis monte vers les plus grands, et garde en mémoire chaque résultat obtenu ⁶.
On commence par définir les sous-problèmes, puis par écrire la relation de récurrence, avant de choisir une version descendante ou ascendante ⁶.
Le gain vient du fait qu'un même sous-problème n'est calculé qu'une seule fois, alors que la récursivité naïve le recalcule sans cesse ⁶.
Les exercices vont du calcul d'un terme de la suite de Fibonacci jusqu'à la plus longue sous-chaîne commune, en passant par la monnaie et le sac à dos.

Comment utiliser ces exercices

Ces exercices te font pratiquer la programmation dynamique. Le principe : on découpe un problème en parties plus petites, on règle d'abord les plus petites, puis on monte vers les plus grandes, en gardant en mémoire ce qu'on a trouvé en chemin ⁶. Les exercices sont rangés par difficulté croissante : ceux de niveau 1 fixent le vocabulaire sur la suite de Fibonacci, ceux de niveau 2 demandent d'écrire une vraie récurrence, ceux de niveau 3 mélangent tableau à deux dimensions et raisonnement sur les indices.

Chaque exercice a un ou deux indices. Cherche d'abord seul pendant quelques minutes, sur papier, avant d'ouvrir un indice, puis compare avec la correction rédigée étape par étape.

MéthodeLa démarche à suivre à chaque fois

Pour un problème d'optimisation ou de dénombrement, applique toujours le même enchaînement :

Définir les sous-problèmes : quelle quantité plus petite sait-on calculer ? Par exemple « le minimum pour une somme $s$ » ou « la valeur pour les $i$ premiers objets ».
Écrire la relation de récurrence : comment la réponse au problème s'obtient-elle à partir des réponses aux sous-problèmes ? Les ressources sur la méthode en font une étape à part entière ⁴.
Fixer les cas de base, c'est-à-dire les plus petits sous-problèmes dont la réponse est connue.
Choisir le sens du calcul : le paradigme propose une méthode ascendante (on remplit un tableau des plus petits aux plus grands) ou descendante (on part du problème et on mémorise au fil de la récursivité) ⁶.
Lire la réponse dans la case qui correspond au problème initial.

Les exercices

Exercice 1 Combien d'appels pour le Fibonacci naïf ?

★☆☆Environ 10 min

La suite de Fibonacci est définie par $F_0 = 0$ , $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$ pour $n \geq 2$ ⁶. On écrit la fonction récursive naïve :

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

On note $C(n)$ le nombre total d'appels de la fonction fib (le premier compris) provoqués par l'appel fib(n).

Donne $C(0)$ et $C(1)$ .
Établis une relation entre $C(n)$ , $C(n-1)$ et $C(n-2)$ .
Calcule $C(5)$ .

Indice 1

Pour $n \geq 2$ , l'appel fib(n) compte pour 1, puis il déclenche fib(n - 1) et fib(n - 2).

Indice 2

Calcule les valeurs de $C(2)$ , $C(3)$ , $C(4)$ dans l'ordre, comme dans un tableau.

Voir la correction pas à pas

Pour $n = 0$ ou $n = 1$ , la fonction renvoie directement : un seul appel, donc $C(0) = C(1) = 1$ .
Pour $n \geq 2$ , on compte l'appel lui-même, plus tous les appels déclenchés par fib(n - 1), plus ceux déclenchés par fib(n - 2) : $C(n) = 1 + C(n-1) + C(n-2)$ .
On calcule de proche en proche : $C(2) = 1 + 1 + 1 = 3$ .
$C(3) = 1 + C(2) + C(1) = 1 + 3 + 1 = 5$ .
$C(4) = 1 + C(3) + C(2) = 1 + 5 + 3 = 9$ .
$C(5) = 1 + C(4) + C(3) = 1 + 9 + 5 = 15$ .

Pour calculer seulement $F_5 = 5$ , la version naïve fait 15 appels. Ce nombre grossit très vite avec $n$ , car les mêmes sous-problèmes (fib(2), fib(3)…) sont recalculés de nombreuses fois : c'est le défaut de la méthode diviser pour régner quand les sous-problèmes se recoupent ⁶.

Exercice 2 Remplir un tableau de Fibonacci

★☆☆Environ 8 min

On calcule $F_{10}$ en méthode ascendante, avec $F_0 = 0$ et $F_1 = 1$ ⁶.

Écris la boucle Python qui remplit un tableau T de taille 11 des plus petits indices aux plus grands.
Remplis à la main le tableau pour les indices de 0 à 10.
Quelle valeur renvoie le programme pour $n = 10$ ?

Indice 1

Les deux premières cases sont les cas de base : T[0] = 0 et T[1] = 1.

Indice 2

Chaque case suivante est la somme des deux cases précédentes.

Voir la correction pas à pas

On initialise T = [0] * 11, puis T[1] = 1.
La boucle est for i in range(2, 11): T[i] = T[i-1] + T[i-2].
On remplit : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 pour les indices 0 à 10.
Le programme renvoie T[10], soit 55.

Chaque case n'est calculée qu'une seule fois, à partir de cases déjà remplies. C'est le principe de la méthode ascendante : on avance dans l'ordre croissant et chaque résultat reste disponible pour les cases suivantes ⁶. Il suffit ici de 9 additions, alors que la version naïve de l'exercice 1 ferait 177 appels récursifs pour $n = 10$ .

Exercice 3 Mémoïsation : compter les additions

★☆☆Environ 10 min

On programme maintenant fib en version descendante avec un dictionnaire memo : avant tout calcul, on regarde si n est déjà dans memo ; sinon on calcule, on range le résultat dans memo, puis on le renvoie. Les cas n = 0 et n = 1 sont renvoyés directement, sans addition.

On appelle fib(8) avec un dictionnaire initialement vide. Combien d'additions le programme effectue-t-il au total ?

Indice 1

Une addition est faite chaque fois qu'une valeur $F_k$ avec $k \geq 2$ est calculée pour la première fois.

Indice 2

Une valeur déjà présente dans memo est simplement relue, sans addition.

Voir la correction pas à pas

L'appel fib(8) descend jusqu'à fib(1) et fib(0) en passant par toutes les valeurs intermédiaires.
Les valeurs qui demandent une addition sont $F_2, F_3, \dots, F_8$ .
Chacune est calculée une seule fois, puis stockée dans memo ; les appels suivants la relisent sans calcul.
Le nombre d'additions est donc le nombre d'indices de 2 à 8, soit $8 - 2 + 1 = 7$ .

La mémoïsation conserve les résultats déjà obtenus pour ne pas les refaire : on garde la structure récursive, mais chaque sous-problème n'est résolu qu'une fois. Le nombre d'additions est proportionnel à $n$ , alors que la version naïve explose.

Exercice 4 Monter un escalier

★★☆Environ 15 min

Léa monte un escalier de $n$ marches. À chaque pas, elle monte soit une marche, soit deux marches. On note $W(n)$ le nombre de façons différentes d'atteindre le haut d'un escalier de $n$ marches.

Donne $W(0)$ et $W(1)$ (on convient qu'il y a une seule façon de ne pas bouger).
Justifie que $W(n) = W(n-1) + W(n-2)$ pour $n \geq 2$ .
Calcule $W(7)$ .

Indice 1

Regarde le tout dernier pas de Léa : de quelle marche vient-elle ?

Indice 2

Les valeurs ressemblent à une suite que tu connais déjà, décalée d'un cran.

Voir la correction pas à pas

Pour 0 marche, une seule façon (ne rien faire) : $W(0) = 1$ . Pour 1 marche, un seul pas simple : $W(1) = 1$ .
Pour $n \geq 2$ , le dernier pas part soit de la marche $n-1$ (pas simple), soit de la marche $n-2$ (pas double). Ces deux cas sont distincts et couvrent tout.
Le nombre de façons d'arriver à la marche $n-1$ est $W(n-1)$ , celui d'arriver à la marche $n-2$ est $W(n-2)$ : on additionne, d'où la relation.
On calcule : $W(2) = 2$ , $W(3) = 3$ , $W(4) = 5$ , $W(5) = 8$ , $W(6) = 13$ .
Enfin $W(7) = W(6) + W(5) = 13 + 8 = 21$ .

Ici, le sous-problème est « atteindre la marche $k$ » et la récurrence découle d'un raisonnement sur le dernier pas. On retrouve la forme de la suite de Fibonacci ⁶ : $W(n) = F_{n+1}$ . Reconnaître une récurrence connue fait gagner du temps, mais il faut toujours la justifier.

Exercice 5 Chemins dans une grille

★★☆Environ 15 min

Une grille compte 4 lignes et 5 colonnes de cases. Un jeton part de la case en haut à gauche et doit atteindre la case en bas à droite, en se déplaçant uniquement d'une case vers la droite ou d'une case vers le bas.

On note $P(i, j)$ le nombre de chemins menant à la case de la ligne $i$ et de la colonne $j$ (numérotées à partir de 0).

Donne $P(0, j)$ et $P(i, 0)$ .
Écris la relation de récurrence pour $i \geq 1$ et $j \geq 1$ .
Combien y a-t-il de chemins jusqu'à la case d'arrivée ?

Indice 1

Pour entrer dans une case, on vient soit de la case au-dessus, soit de la case à gauche.

Indice 2

Remplis le tableau ligne par ligne : la première ligne et la première colonne ne contiennent que des 1.

Voir la correction pas à pas

Sur la première ligne, on ne peut arriver que par la gauche : un seul chemin, donc $P(0, j) = 1$ . De même $P(i, 0) = 1$ .
Pour $i, j \geq 1$ , on arrive d'en haut ou de la gauche : $P(i, j) = P(i-1, j) + P(i, j-1)$ .
Ligne 1 : 1, 2, 3, 4, 5.
Ligne 2 : 1, 3, 6, 10, 15.
Ligne 3 : 1, 4, 10, 20, 35.
La case d'arrivée est $P(3, 4) = 35$ .

Le tableau à deux dimensions est le réflexe de la méthode ascendante : chaque case dépend de cases déjà remplies, donc on les remplit dans l'ordre. Le nombre de cases à calculer est $4 \times 5 = 20$ , bien moins que d'énumérer un par un les 35 chemins.

Exercice 6 Rendu de monnaie avec des pièces 1, 3 et 4

★★☆Environ 20 min

Un distributeur dispose de pièces de valeurs faciales 1, 3 et 4 en quantité illimitée. On cherche le nombre minimal de pièces pour rendre une somme $s$ . On note $M(s)$ ce minimum, avec $M(0) = 0$ .

La version récursive s'appuie sur la remarque suivante : si l'on retire une pièce de valeur $x$ de la somme, il reste à rendre $s - x$ , ce qui donne mini = min(mini, 1 + dynRecursif(valeursFaciales, somme - x)) ².

Écris la relation de récurrence de $M(s)$ .
Calcule $M(1)$ jusqu'à $M(6)$ .
Pour $s = 6$ , compare avec la stratégie gloutonne qui prend toujours la plus grande pièce possible.

Indice 1

Pour $M(s)$ , essaie chaque pièce $x \leq s$ et garde la meilleure option : $1 + M(s - x)$ .

Indice 2

La stratégie gloutonne pour 6 donne 4, puis 1, puis 1.

Voir la correction pas à pas

Relation : $M(s) = 1 + \min\limits_{x \in \{1, 3, 4\},\ x \leq s} M(s - x)$ , avec $M(0) = 0$ .
$M(1) = 1 + M(0) = 1$ .
$M(2) = 1 + M(1) = 2$ .
$M(3) = 1 + \min(M(2), M(0)) = 1$ .
$M(4) = 1 + \min(M(3), M(1), M(0)) = 1$ .
$M(5) = 1 + \min(M(4), M(2), M(1)) = 1 + 1 = 2$ .
$M(6) = 1 + \min(M(5), M(3), M(2)) = 1 + \min(2, 1, 2) = 2$ : c'est 3 + 3.
Le glouton rend 4 + 1 + 1, soit 3 pièces : il n'est pas optimal.

Le minimum pour 6 est 2 pièces. Le glouton se trompe parce qu'un choix local (la plus grande pièce) n'est pas toujours compatible avec la meilleure solution globale. La programmation dynamique compare tous les choix possibles pour chaque sous-problème, ce qui rejoint le principe d'optimalité : une solution optimale se construit à partir de solutions optimales de sous-problèmes ⁶.

Exercice 7 Sac à dos : remplir le tableau

★★★Environ 25 min

Dans le problème du sac à dos, on dispose de $n$ objets, chacun avec un poids $w_i$ et une valeur $c_i$ , et d'un sac de capacité limitée ; on cherche à maximiser la valeur emportée ⁴. Ce problème classique est NP-difficile, mais un algorithme de programmation dynamique le résout en temps pseudo-polynomial ⁶.

On considère quatre objets (poids ; valeur) : $A (2 ; 3)$ , $B (3 ; 4)$ , $C (4 ; 5)$ , $D (5 ; 6)$ , et un sac de capacité 7.

On note $V(i, c)$ la valeur maximale avec les $i$ premiers objets et une capacité $c$ .

Écris la relation de récurrence de $V(i, c)$ et les cas de base.
Calcule la valeur maximale pour la capacité 7.
Quels objets choisit-on ?

Indice 1

Pour l'objet $i$ , deux choix : ne pas le prendre ( $V(i-1, c)$ ), ou le prendre si $w_i \leq c$ ( $c_i + V(i-1, c - w_i)$ ).

Indice 2

Tu peux aussi énumérer les parties de poids total au plus 7 pour vérifier ton tableau.

Voir la correction pas à pas

Cas de base : $V(0, c) = 0$ pour tout $c$ , et $V(i, 0) = 0$ .
Récurrence : si $w_i > c$ , $V(i, c) = V(i-1, c)$ ; sinon $V(i, c) = \max\big(V(i-1, c),\ c_i + V(i-1, c - w_i)\big)$ .
Avec $A$ seul, pour $c = 2$ à 7 : $V(1, c) = 3$ .
Avec $A$ et $B$ : $V(2, c)$ vaut 0 pour $c<2$ , 3 pour $c = 2$ , 4 pour $c = 3$ et $c=4$ , 7 pour $c \geq 5$ .
Avec $A$ , $B$ , $C$ : $V(3, 7) = \max(V(2, 7),\ 5 + V(2, 3)) = \max(7, 5 + 4) = 9$ .
Avec $D$ aussi : $V(4, 7) = \max(V(3, 7),\ 6 + V(3, 2)) = \max(9, 6 + 3) = 9$ .
Le maximum est 9. Il s'obtient avec $B$ et $C$ (poids $3 + 4 = 7$ , valeur $4 + 5 = 9$ ) ou avec $A$ et $D$ (poids $2 + 5 = 7$ , valeur $3 + 6 = 9$ ).

La valeur maximale est 9, obtenue de deux façons différentes. Le tableau contient $(n+1)(W+1)$ cases pour $n$ objets et une capacité $W$ : son coût dépend de la valeur numérique de $W$ , ce qui explique le qualificatif « pseudo-polynomial » ⁶.

Exercice 8 Plus longue sous-chaîne commune

★★★Environ 25 min

Étant donné deux textes $x$ et $y$ , on cherche une plus longue sous-chaîne commune, problème que l'on peut traiter par la programmation dynamique ². Dans cet exercice, une sous-chaîne est une suite de lettres consécutives dans le texte.

On prend $x = \text{INFORMATIQUE}$ et $y = \text{FORMULE}$ . On note $L(i, j)$ la longueur de la plus longue sous-chaîne commune qui se termine à la lettre $x_i$ de $x$ et à la lettre $y_j$ de $y$ (les lettres sont numérotées à partir de 1).

Écris la relation de récurrence de $L(i, j)$ et le cas de base.
Explique comment lire la réponse dans le tableau.
Détermine la longueur de la plus longue sous-chaîne commune et donne-la.

Indice 1

Si les lettres $x_i$ et $y_j$ sont différentes, aucune sous-chaîne commune ne peut se terminer ici.

Indice 2

Si elles sont égales, on prolonge la sous-chaîne qui se terminait juste avant, aux positions $i-1$ et $j-1$ .

Voir la correction pas à pas

Cas de base : $L(0, j) = L(i, 0) = 0$ (texte vide).
Si $x_i = y_j$ , alors $L(i, j) = 1 + L(i-1, j-1)$ ; sinon $L(i, j) = 0$ .
La réponse n'est pas forcément dans la dernière case : une sous-chaîne peut se terminer n'importe où, donc on prend le maximum de toutes les cases.
Dans $x = \text{INFORMATIQUE}$ , les lettres F, O, R, M se suivent aux positions 3 à 6 ; dans $y$ , elles occupent les positions 1 à 4.
Les valeurs de $L$ sur cette diagonale sont $L(3, 1) = 1$ , $L(4, 2) = 2$ , $L(5, 3) = 3$ , $L(6, 4) = 4$ .
Après M, $x$ continue par A et $y$ par U : $L(7, 5) = 0$ . Les autres diagonales restent bien plus courtes, car le reste de $y$ (ULE) ne partage avec $x$ que des lettres isolées.
La plus longue sous-chaîne commune est « FORM », de longueur 4.

Ici encore, le sous-problème est défini par deux indices, ce qui donne un tableau à deux dimensions. Le piège est le travail sur les indices, souvent plus délicat que l'idée de la récurrence elle-même ². Retiens que, pour des lettres consécutives, la case retombe à 0 en cas de différence, et que la réponse est le maximum du tableau.

Les questions qu'on se pose

Comment savoir si un problème relève de la programmation dynamique ?

Cherche deux signes : le problème se décompose en sous-problèmes plus petits, et ces sous-problèmes se recoupent (on retomberait plusieurs fois sur le même). Si les sous-problèmes sont indépendants, la méthode diviser pour régner suffit ⁶. Un autre signe est le principe d'optimalité : la solution optimale se construit en combinant des solutions optimales de sous-problèmes ⁶. Pour un problème d'optimisation (minimum, maximum) dont les sous-problèmes se recoupent, pense à cette méthode.

Quelle différence entre version ascendante et version descendante ?

Dans la version ascendante, tu remplis un tableau des plus petits sous-problèmes vers les plus grands, avec une boucle. Dans la version descendante, tu écris la fonction récursive et tu mémorises chaque résultat pour ne pas le recalculer (mémoïsation) ⁶. Les deux calculent chaque sous-problème une seule fois. La première évite la récursivité et ses limites de profondeur ; la seconde est souvent plus proche de la formule de récurrence.

Que faut-il écrire sur la copie au bac pour une question de programmation dynamique ?

Écris dans cet ordre : ce que représente chaque case du tableau (le sous-problème), la relation de récurrence, les cas de base, le sens de remplissage, puis la case qui contient la réponse. Une récurrence correcte sans cas de base ou sans définition du sous-problème perd facilement des points. Termine par le calcul effectif du tableau, rempli ligne par ligne.

Sources

Programme visé : Programme de l'enseignement de spécialité de numérique et sciences informatiques de la classe terminale de la voie générale · Bulletin officiel de l'Éducation nationale

Programme de l'enseignement de spécialité de numérique et sciences informatiques de la classe terminale de la voie générale, Bulletin officiel de l'Éducation nationale. Consulté le 7 novembre 2026.
Ressource Éduscol - Programmation dynamique (Terminale NSI), eduscol.education.gouv.fr. Consulté le 7 novembre 2026.
Programmes et ressources en numérique et sciences informatiques - voie générale, eduscol.education.gouv.fr. Consulté le 7 novembre 2026.
Recherche Opérationnelle - Programmation Dynamique, CNRS (Université Lyon). Consulté le 7 novembre 2026.
Programmation dynamique et mémoïsation, CNRS. Consulté le 7 novembre 2026.
Programmation dynamique, Wikipédia. Consulté le 7 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Programmation dynamique : exercices corrigés de Terminale NSI

L'essentiel

Comment utiliser ces exercices

Les exercices

Exercice 1 Combien d'appels pour le Fibonacci naïf ?

Exercice 2 Remplir un tableau de Fibonacci

Exercice 3 Mémoïsation : compter les additions

Exercice 4 Monter un escalier

Exercice 5 Chemins dans une grille

Exercice 6 Rendu de monnaie avec des pièces 1, 3 et 4

Exercice 7 Sac à dos : remplir le tableau

Exercice 8 Plus longue sous-chaîne commune

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur