Programmation dynamique NSI : guide complet pour lycéens

La programmation dynamique est une technique puissante qui permet de résoudre des problèmes complexes en les découpant en sous-problèmes plus simples. En NSI, tu la rencontreras souvent en Terminale, et elle peut te sembler abstraite au premier abord. Pas de panique ! Dans ce guide, on va démystifier ensemble cette notion, avec des exemples concrets en Python et des astuces pour bien la maîtriser. Prêt à devenir un as de la programmation dynamique ? C'est parti !

Qu'est-ce que la programmation dynamique ?

La programmation dynamique (souvent abrégée en DP pour Dynamic Programming) est une méthode algorithmique qui consiste à résoudre un problème en le décomposant en sous-problèmes plus petits, puis en mémorisant les résultats de ces sous-problèmes pour éviter de les recalculer plusieurs fois. C'est une optimisation de la récursivité naïve, qui peut être extrêmement inefficace si on recalcule sans cesse les mêmes choses.

Imagine que tu doives calculer le nombre de chemins possibles pour aller d'un coin à un autre d'une grille, en ne te déplaçant que vers le bas ou vers la droite. Si tu utilises une récursion naïve, tu vas explorer un nombre exponentiel de chemins. Avec la programmation dynamique, tu vas calculer le nombre de chemins pour chaque case une seule fois, puis les réutiliser. Résultat : un algorithme en temps polynomial, beaucoup plus rapide !

En NSI, tu verras notamment deux grandes approches :

• La mémoïsation (ou mémorisation) : on part du problème initial et on descend récursivement, mais on stocke les résultats déjà calculés dans un tableau (souvent un dictionnaire ou une liste) pour ne pas les recalculer.
• La tabulation (ou bottom-up) : on construit la solution en partant des cas de base, et on remplit un tableau itérativement jusqu'à arriver à la solution finale.

Ces deux méthodes reposent sur le même principe : éviter les calculs redondants. On parle de recouvrement de sous-problèmes (overlapping subproblems) et de sous-structure optimale (optimal substructure). Ce sont les deux conditions pour qu'un problème soit résoluble par programmation dynamique.

Exemple classique : la suite de Fibonacci

La suite de Fibonacci est l'exemple parfait pour comprendre la programmation dynamique. La définition est simple : F(0) = 0, F(1) = 1, et pour n > 1, F(n) = F(n-1) + F(n-2).

Si on écrit une fonction récursive naïve :

def fibo_naif(n):
    if n <= 1:
        return n
    return fibo_naif(n-1) + fibo_naif(n-2)

Cette fonction est très lente pour n un peu grand (comme 40), car elle recalcule énormément de fois les mêmes valeurs. Par exemple, pour calculer fibo(5), on calcule fibo(4) et fibo(3), mais fibo(3) est recalculé plusieurs fois. Le nombre d'appels explose exponentiellement.

Voyons maintenant la version avec mémoïsation :

def fibo_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
    return memo[n]

Ici, on stocke chaque résultat dans le dictionnaire memo. Ainsi, chaque valeur n'est calculée qu'une seule fois. La complexité devient linéaire en n, c'est-à-dire O(n). C'est un gain énorme !

Et voici la version tabulaire (itérative) :

def fibo_tab(n):
    if n <= 1:
        return n
    tab = [0] * (n+1)
    tab[1] = 1
    for i in range(2, n+1):
        tab[i] = tab[i-1] + tab[i-2]
    return tab[n]

Cette version remplit un tableau de taille n+1 et utilise une simple boucle. C'est souvent plus efficace en pratique car il n'y a pas de récursion, donc pas de risque de dépassement de la pile d'appels.

En NSI, tu n'as pas besoin de connaître toutes les subtilités théoriques, mais tu dois savoir expliquer l'idée et implémenter ces deux versions. C'est un grand classique des épreuves !

Cas d'usage concret : le problème du rendu de monnaie

Un autre exemple très parlant est le problème du rendu de monnaie. Imagine que tu disposes de pièces de certaines valeurs (par exemple 1, 2, 5, 10) et que tu dois rendre une somme donnée (par exemple 14) avec le minimum de pièces possible.

Une approche gloutonne (prendre la plus grosse pièce à chaque fois) ne donne pas toujours le résultat optimal. Par exemple, avec des pièces de 1, 3 et 4, pour rendre 6, l'approche gloutonne donnerait 4 + 1 + 1 (3 pièces), alors que la solution optimale est 3 + 3 (2 pièces).

La programmation dynamique résout ce problème parfaitement. On définit min_pieces(s) comme le nombre minimal de pièces pour rendre la somme s. La relation de récurrence est :

min_pieces(s) = 1 + min(min_pieces(s - pièce) pour chaque pièce ≤ s)

avec min_pieces(0) = 0.

Voici une implémentation en Python avec mémoïsation :

def rendu_monnaie(somme, pieces, memo=None):
    if memo is None:
        memo = {}
    if somme in memo:
        return memo[somme]
    if somme == 0:
        return 0
    meilleur = float('inf')
    for p in pieces:
        if p <= somme:
            nb = rendu_monnaie(somme - p, pieces, memo)
            if nb + 1 < meilleur:
                meilleur = nb + 1
    memo[somme] = meilleur
    return meilleur

Et la version tabulaire :

def rendu_monnaie_tab(somme, pieces):
    # Initialisation avec une valeur infinie
    tab = [float('inf')] * (somme + 1)
    tab[0] = 0
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s:
                tab[s] = min(tab[s], tab[s - p] + 1)
    return tab[somme]

Teste par toi-même avec somme=6 et pieces=[1,3,4] : tu obtiendras 2. C'est magique, non ?

Programmation dynamique et récursivité : quelle différence ?

Tu as peut-être déjà vu la récursivité en NSI (notamment en Première). La programmation dynamique est souvent présentée comme une amélioration de la récursivité. En fait, toute solution de programmation dynamique peut être vue comme une récursivité avec mémorisation, ou comme une itération.

La clé, c'est de comprendre que la programmation dynamique s'applique quand un problème a une sous-structure optimale (la solution optimale du problème global est composée de solutions optimales de sous-problèmes) et que les sous-problèmes se chevauchent (le même sous-problème apparaît plusieurs fois).

Par exemple, dans le calcul de Fibonacci, fibo(3) est utilisé pour calculer fibo(4) et fibo(5). C'est ce chevauchement qui rend la mémoïsation utile.

En revanche, des algorithmes comme le tri rapide (quicksort) ou le tri fusion (merge sort) utilisent la récursivité mais ne sont pas de la programmation dynamique, car les sous-problèmes sont indépendants (ils ne se chevauchent pas).

Comment reconnaître un problème de programmation dynamique ?

Au bac, on te demandera parfois de reconnaître si un problème relève de la programmation dynamique. Voici quelques indices :

• Le problème demande une optimisation (maximum, minimum, nombre de possibilités).
• Il peut être décomposé en sous-problèmes similaires.
• Les sous-problèmes se chevauchent (on retrouve les mêmes calculs).
• On peut définir une relation de récurrence entre les solutions.

Par exemple, le problème du sac à dos (choisir des objets avec un poids limité pour maximiser la valeur) est un classique de la programmation dynamique. Le problème du plus long sous-ensemble croissant, le problème du plus court chemin dans un graphe (avec l'algorithme de Dijkstra, bien que celui-ci soit plutôt de type glouton), etc.

Pour t'entraîner, n'hésite pas à consulter nos exercices de NSI et nos fiches de révision qui contiennent des sujets types.

Programmation dynamique au bac NSI : ce qu'il faut savoir

La programmation dynamique figure dans les programmes de Terminale NSI, notamment dans la partie « Algorithmique ». Tu dois être capable de :

• Identifier un problème qui peut être résolu par programmation dynamique.
• Implémenter une solution avec mémoïsation ou tabulation (en Python, mais le langage n'est pas imposé).
• Expliquer la complexité et comparer avec une solution naïve.
• Adapter un algorithme existant (par exemple, transformer une fonction récursive naïve en version avec mémoïsation).

Lors de l'épreuve écrite, il peut y avoir des questions de cours ou des exercices pratiques. Il est essentiel de bien maîtriser les exemples classiques comme Fibonacci, le rendu de monnaie, ou le problème du sac à dos (au moins les versions simples).

Pour t'aider, voici quelques conseils de méthode :

• Écris toujours la relation de récurrence avant de coder. C'est la base de tout.
• Commence par une version naïve pour bien comprendre le problème, puis optimise.
• Utilise un dictionnaire pour la mémoïsation ; c'est simple et efficace.
• Pour la tabulation, dessine le tableau sur papier pour visualiser les dépendances.
• Teste avec des petits exemples pour vérifier que ton code est juste.

Si tu as besoin de revoir les bases de la récursivité ou de l'algorithmique, rends-toi sur notre page de cours de NSI.

Aller plus loin : d'autres exemples pour t'entraîner

Voici deux autres problèmes classiques que tu peux résoudre en programmation dynamique pour t'entraîner :

Le problème du saut de grenouille

Une grenouille doit traverser une rivière en sautant sur des nénuphars. Chaque nénuphar a une valeur (un nombre de points). La grenouille peut sauter d'un nénuphar à un autre si la distance est inférieure ou égale à une certaine valeur. Le but est de maximiser le score total. C'est un problème de plus long chemin dans un graphe acyclique, qui se résout par programmation dynamique.

Le plus long palindrome

Étant donné une chaîne de caractères, trouver la longueur du plus long palindrome (mot qui se lit dans les deux sens) qui soit une sous-séquence (pas nécessairement contiguë). Par exemple, pour « BBABCBCAB », le plus long palindrome est « BACBCAB » (longueur 7). La relation de récurrence est : si les caractères aux extrémités sont égaux, on ajoute 2, sinon on prend le max entre la chaîne privée du premier caractère et celle privée du dernier.

Ces problèmes te permettront de bien comprendre la mécanique. N'hésite pas à les coder toi-même !

Conclusion : la programmation dynamique, un atout pour ton avenir

La programmation dynamique est une compétence précieuse, non seulement pour le bac, mais aussi pour des études supérieures en informatique. Elle t'apprend à réfléchir de manière structurée et à optimiser tes algorithmes. Avec un peu de pratique, tu verras que ce n'est pas si sorcier !

Alors, lance-toi : ouvre ton éditeur Python, implémente les exemples de cet article, puis essaie de résoudre des problèmes plus complexes. Tu peux aussi t'entraîner sur des plateformes en ligne comme France IOI ou Prologin. Et si tu as besoin d'aide, n'oublie pas que des ressources comme Allo Lycée peuvent t'accompagner.

La programmation dynamique est un vrai super-pouvoir. Utilise-le à bon escient !