Programmation dynamique : relations de récurrence et tableaux auxiliaires (Bac NSI)

Mis à jour le · AprenAI

La programmation dynamique résout un problème en mémorisant les résultats de sous-problèmes plus petits, pour ne pas les recalculer. Au Bac NSI, les annales digitalisées en comptent 2 sujets : la plus grande somme d'une sous-séquence (2021, 4 points) et la plus grande base carrée d'une carte (2025, 6 points). Dans les deux cas, une méthode exhaustive est d'abord proposée, puis remplacée par une relation de récurrence.

Comment fonctionne la programmation dynamique ?

Le principe tient en trois idées. D'abord on définit une quantité intermédiaire, par exemple S(i), la plus grande somme d'une sous-séquence qui se termine à l'indice i. Ensuite on écrit une relation de récurrence qui calcule cette quantité à partir de valeurs déjà connues. Enfin on stocke les valeurs dans un tableau (liste ou liste de listes) et on les calcule dans un ordre tel que chaque valeur n'utilise que des cases déjà remplies.

Premier exemple (Métropole Candidat libre 2, 2021, exercice 5) : trouver la plus grande somme d'éléments voisins d'un tableau d'entiers relatifs. Si tous les éléments sont positifs, la solution est la somme de tout le tableau ; s'ils sont tous négatifs, c'est le plus grand élément, une sous-séquence d'un seul élément. L'approche exhaustive examine toutes les sous-séquences avec deux boucles i et j : pour un tableau de 10 éléments, le corps de la boucle imbriquée s'exécute 10 + 9 + ... + 1 = 55 fois, et il faut en plus calculer chaque somme. La version dynamique définit S(0) = lst[0] puis S(i) = lst[i] si S(i-1) ≤ 0, sinon S(i) = lst[i] + S(i-1). La réponse est le maximum des S(i), calculé en une seule boucle : complexité linéaire O(n), contre O(n²) au moins pour l'approche exhaustive. Sur l'exemple du sujet, la sous-séquence 6 ; 8 ; -6 ; 10 donne 18.

Second exemple (Métropole France 1 remplacement, 2025, exercice 2) : une carte n × n est une liste de listes de 0 et de 1, et l'on cherche le plus grand carré ne contenant que des 1. Sur la carte_A du sujet, la plus grande base a pour côté 3 et son coin supérieur gauche est en (2, 1). La recherche exhaustive teste tous les carrés : il y en a n(n+1)(2n+1)/6, et chaque test parcourt taille² cellules, ce qui explose vite : le sujet note qu'à n = 300 on dépasse déjà 9 millions de carrés. La solution dynamique remplit un tableau auxiliaire aux où aux[i][j] est le côté du plus grand carré de 1 dont (i, j) est le coin supérieur gauche. Si carte[i][j] vaut 0, alors aux[i][j] = 0 ; sur la dernière ligne et la dernière colonne, aux reprend la valeur de carte ; sinon aux[i][j] = 1 + min(aux[i][j+1], aux[i+1][j], aux[i+1][j+1]). On remplit du bas vers le haut et de droite à gauche, puis on cherche le maximum de aux.

Vérification sur carte_B = [[1,1,1,1],[0,1,1,1],[0,1,1,1],[1,0,1,1]] : on obtient aux = [[1,3,2,1],[0,2,2,1],[0,1,2,1],[1,0,1,1]]. Le maximum est 3, en position (0, 1) : la plus grande base est de taille 3.

À ne pas confondre en programmation dynamique

ProblèmeApproche exhaustiveApproche dynamique
Somme maximale d'une sous-séquenceToutes les paires (i, j) : au moins O(n²)Une boucle avec S(i) : O(n)
Plus grande base carréeTous les carrés de toutes les taillesaux[i][j] = 1 + min des trois voisins, calculé une fois par case

Mode Bac : ce qui rapporte des points

Quels exercices sont tombés sur la programmation dynamique ?

Dans les annales digitalisées, le thème apparaît 2 fois : en 2021 (4 points) et en 2025 (6 points). Les deux exercices suivent le même scénario : un problème d'optimisation, une résolution exhaustive à coder, l'analyse de son coût, puis la version dynamique à appliquer à la main et à compléter.

Entraîne-toi : Programmation dynamique (7 sujets officiels)

Tous les sujets de NSI sur « Programmation dynamique » (2021-2026), avec le corrigé.

Comment appliquer une relation de récurrence en programmation dynamique ?

Exemple : Métropole France 1 remplacement, 2025, exercice 2, partie B, avec carte_B. Il faut remplir le tableau auxiliaire aux.

  1. Initialiser les bords: La dernière ligne et la dernière colonne de aux reprennent carte : [1, 0, 1, 1] pour la dernière ligne de carte_B, et 1 pour chaque dernière colonne.
  2. Parcourir en sens inverse: Partez du coin inférieur droit, remontez ligne par ligne et allez de droite à gauche : les trois voisins sont déjà calculés.
  3. Traiter un 0: Si carte[i][j] vaut 0, aux[i][j] vaut 0 : par exemple carte_B[1][0] = 0 donne aux_B[1][0] = 0.
  4. Appliquer la formule: Pour un 1, calculez 1 + min des trois voisins. En (0, 1) de carte_B : 1 + min(2, 2, 2) = 3.
  5. Lire la réponse: Le maximum de aux vaut 3 : la plus grande base carrée a pour côté 3, avec pour coin supérieur gauche la cellule (0, 1).
  6. Justifier le gain: Chaque case est calculée une seule fois à partir de trois voisines : le nombre d'opérations est proportionnel au nombre de cases, alors que l'exhaustif teste des millions de carrés.

Quelles erreurs éviter en programmation dynamique ?

Les corrigés sont des réponses types sans barème détaillé ; ils montrent les points sur lesquels les réponses doivent être précises : bornes, initialisation et expression exacte de la récurrence.

Comment réviser la programmation dynamique ?

  1. Refaire les deux récurrences à la main: Sur un tableau de dix éléments puis sur une carte 4 × 4, jusqu'à retrouver les valeurs sans hésiter.
  2. Écrire les deux fonctions Python: Une boucle qui construit sommes_max et le maximum ; une double boucle qui remplit aux de bas en haut.
  3. Savoir compter les opérations: La somme 1 + 2 + ... + n vaut n(n+1)/2 : c'est un classique des questions de coût.
  4. Comparer exhaustif et dynamique: Pour chaque problème, préparez une phrase sur la différence de coût.
  5. S'entraîner sur AprenAI: Faites les deux exercices officiels du thème, puis le plus proche sujet complet.

Qu'est-ce que la programmation dynamique ?

C'est une méthode qui résout un problème à partir de résultats de sous-problèmes stockés dans un tableau, afin de ne calculer chaque résultat qu'une fois.

Comment trouver la plus grande somme d'une sous-séquence ?

On calcule S(i) : lst[i] si S(i-1) est négatif ou nul, sinon lst[i] + S(i-1). La réponse est le plus grand S(i). Le coût est linéaire.

Quelle différence entre recherche exhaustive et programmation dynamique ?

L'exhaustive teste toutes les solutions ; la dynamique mémorise les résultats partiels. Au Bac, la première est quadratique ou pire, la seconde linéaire ou proportionnelle au nombre de cases.

Combien de sujets de Bac NSI portent sur la programmation dynamique ?

Dans les annales digitalisées, 2 sujets : un de 4 points en 2021 et un de 6 points en 2025.

Comment remplir le tableau auxiliaire de la plus grande base carrée ?

On part du coin inférieur droit. Un 0 de la carte donne 0, un 1 donne 1 plus le minimum des trois voisins (droite, dessous, diagonale). Le maximum du tableau est le côté de la plus grande base.

Plus sur l'épreuve de NSI