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.
- 7 sujets officiels
- 1,4 % des sujets
- 2021-2026 années
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.
- Programmation dynamique: Méthode qui résout un problème à partir de sous-problèmes dont on mémorise les résultats pour ne pas les recalculer.
- Relation de récurrence: Formule qui exprime une valeur à partir de valeurs précédentes, comme S(i) à partir de S(i-1).
- Recherche exhaustive: Méthode qui teste toutes les solutions possibles, simple mais souvent trop coûteuse.
- Tableau auxiliaire: Liste ou liste de listes qui stocke les résultats intermédiaires (sommes_max, aux).
- Sous-séquence: Suite non vide d'éléments voisins d'un tableau.
- Complexité temporelle: Ordre de grandeur du nombre d'opérations en fonction de la taille n des données.
À ne pas confondre en programmation dynamique
- Exhaustif ≠ Dynamique: L'exhaustif teste toutes les solutions et refait les mêmes calculs ; le dynamique mémorise les résultats intermédiaires et ne calcule chaque case qu'une fois.
- Programmation dynamique ≠ Diviser pour régner: Diviser pour régner découpe en sous-problèmes indépendants ; en dynamique, les sous-problèmes se recouvrent et leurs résultats sont réutilisés.
- Sous-séquence ≠ Sous-ensemble: Une sous-séquence est faite d'éléments voisins, contigus, dans le tableau ; ce n'est pas un choix libre d'éléments.
- S(i) ≠ Réponse finale: S(i) est la meilleure somme qui se termine en i ; la réponse est le maximum de tous les S(i), pas S(n-1).
- Taille du carré ≠ Nombre de cases: Un carré de côté taille contient taille × taille cellules, donc la somme de ses valeurs est taille ** 2 s'il ne contient que des 1.
| Problème | Approche exhaustive | Approche dynamique |
|---|---|---|
| Somme maximale d'une sous-séquence | Toutes les paires (i, j) : au moins O(n²) | Une boucle avec S(i) : O(n) |
| Plus grande base carrée | Tous les carrés de toutes les tailles | aux[i][j] = 1 + min des trois voisins, calculé une fois par case |
Mode Bac : ce qui rapporte des points
- Relation de la somme maximale: S(i) = lst[i] si S(i-1) ≤ 0, sinon S(i) = lst[i] + S(i-1). Le maximum des S(i) est la réponse.
- Relation de la base carrée: aux[i][j] = 1 + min(aux[i][j+1], aux[i+1][j], aux[i+1][j+1]) si carte[i][j] vaut 1, et 0 sinon.
- Test d'un carré constructible: La somme des valeurs d'un carré de côté taille vaut taille ** 2 si et seulement si toutes les cases valent 1.
- Compter les exécutions: 10 + 9 + ... + 1 = n(n+1)/2 : 55 pour n = 10.
- Complexité: Exhaustif : quadratique ou pire. Dynamique pour la somme maximale : linéaire, une seule boucle.
- Cas triviaux: Tous positifs : somme du tableau. Tous négatifs : le plus grand élément.
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.
- Somme maximale d'une sous-séquence (1): Cas triviaux (tout positif, tout négatif), code de somme_sous_sequence, nombre de comparaisons de pgsp, modification pour renvoyer aussi les indices, calcul des S(i) sur un exemple et relation de récurrence (Métropole Candidat libre 2, 2021, exercice 5).
- Plus grande base carrée sur une carte (1): Taille et coordonnées d'une base, code de est_constructible, boucles while de la recherche exhaustive, explosion du temps de calcul, puis tableau auxiliaire aux sur carte_B et carte_C (Métropole France 1 remplacement, 2025, exercice 2).
- Exercice 5 · Métropole Candidat libre 2021 (sujet 2) · Somme maximale d'une sous-séquence
- Exercice 2 · Métropole 1 remplacement 2025 · Plus grande base carrée sur une carte
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.
- 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.
- 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.
- 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.
- Appliquer la formule: Pour un 1, calculez 1 + min des trois voisins. En (0, 1) de carte_B : 1 + min(2, 2, 2) = 3.
- 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).
- 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.
- Mal borner la boucle du carré: Le carré de côté taille issu de (i, j) doit rester dans la carte : j + taille <= n, et les colonnes parcourues vont de j_coin à j_coin + taille - 1.
- Oublier d'initialiser: Il faut S(0) = lst[0], et la première cellule est traitée avant d'utiliser S(i-1).
- Renvoyer S(n-1) au lieu du maximum: La sous-séquence optimale peut se terminer n'importe où : prenez le maximum de la liste des S(i).
- Se tromper entre min et max: Pour un carré, la case est limitée par le plus petit de ses voisins : c'est min, pas max.
- Confondre j et i dans les indices: carte[i][j] : i est la ligne, j la colonne. Inverser fait lire un autre carré.
- Ne pas justifier la complexité: Dire « c'est plus rapide » ne suffit pas : indiquer une boucle simple, donc O(n), ou le nombre de carrés à tester.
Comment réviser la programmation dynamique ?
- 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.
- Écrire les deux fonctions Python: Une boucle qui construit sommes_max et le maximum ; une double boucle qui remplit aux de bas en haut.
- Savoir compter les opérations: La somme 1 + 2 + ... + n vaut n(n+1)/2 : c'est un classique des questions de coût.
- Comparer exhaustif et dynamique: Pour chaque problème, préparez une phrase sur la différence de coût.
- 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
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets