Qu'est-ce que la programmation dynamique ?
La programmation dynamique (PD) est une méthode algorithmique puissante pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples. Contrairement à ce que son nom pourrait suggérer, elle n'a rien à voir avec la programmation au sens de l'écriture de code, mais plutôt avec une planification (dynamic programming en anglais). Son principe fondateur est d'éviter les calculs redondants en mémorisant les résultats des sous-problèmes déjà résolus. C'est un pilier de l'algorithmique que tu rencontreras souvent en NSI, notamment pour les problèmes d'optimisation.
Imagine que tu doives calculer un long itinéraire. Au lieu de recalculer à chaque fois le meilleur chemin entre deux points intermédiaires, tu notes les résultats dans un tableau. C'est l'essence de la PD : résoudre chaque sous-problème une seule fois et réutiliser la solution. Elle s'oppose souvent à une approche récursive naïve qui, elle, recalcule les mêmes valeurs un nombre exponentiel de fois.
Le principe fondamental : optimalité et sous-structure
Pour qu'un problème soit résoluble par programmation dynamique, il doit posséder deux propriétés clés :
- La sous-structure optimale : La solution optimale du problème global peut être construite à partir des solutions optimales de ses sous-problèmes. Par exemple, le chemin le plus court passant par un point A est la combinaison du chemin le plus court pour aller à A et de celui pour partir de A.
- Le recouvrement des sous-problèmes (ou chevauchement) : Le problème se décompose en sous-problèmes qui sont résolus plusieurs fois. C'est cette redondance que la PD cherche à éliminer par la mémorisation (memoization).
Il existe deux approches principales pour implémenter la programmation dynamique :
- L'approche ascendante (Bottom-up) : On résout d'abord les plus petits sous-problèmes, et on utilise leurs résultats pour construire les solutions aux problèmes plus grands. C'est souvent fait avec un tableau (un array).
- L'approche descendante avec mémoïsation (Top-down with memoization) : On part du problème initial de manière récursive, mais on stocke le résultat de chaque sous-problème dans un cache (comme un dictionnaire) au premier calcul. Les appels suivants récupèrent directement la valeur mémorisée.
Exemple classique : les nombres de Fibonacci
La suite de Fibonacci est l'exemple pédagogique parfait. Définie par F(0)=0, F(1)=1 et F(n) = F(n-1) + F(n-2) pour n>1. Une implémentation récursive naïve est très inefficace.
Version récursive naïve (inefficace)
Cette version a une complexité exponentielle O(2^n) car elle recalcule sans cesse les mêmes valeurs.
def fib_naif(n): if n <= 1: return n return fib_naif(n-1) + fib_naif(n-2)
Version programmation dynamique (Bottom-up)
On construit un tableau et on le remplit de manière itérative. Complexité linéaire O(n).
def fib_dp_bottom_up(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]
Version avec mémoïsation (Top-down)
On garde la structure récursive, mais on évite les recalculs.
def fib_dp_top_down(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_dp_top_down(n-1, memo) + fib_dp_top_down(n-2, memo) return memo[n]
La différence de performance est astronomique pour n grand !
Un problème incontournable : le sac à dos (0/1)
Le problème du sac à dos est un grand classique de la PD. Tu as un sac d'une capacité maximale de poids W et une liste d'objets, chacun avec un poids et une valeur. L'objectif est de maximiser la valeur totale des objets dans le sac sans dépasser la capacité.
On va utiliser un tableau à deux dimensions dp[i][w] qui représentera la valeur maximale que l'on peut obtenir avec les i premiers objets pour un poids maximal w.
def sac_a_dos(W, poids, valeurs): n = len(valeurs) # Création d'un tableau (n+1) x (W+1) rempli de 0 dp = [[0 for _ in range(W+1)] for _ in range(n+1)] for i in range(1, n+1): for w in range(1, W+1): # Si le poids de l'objet i-1 est inférieur ou égal à la capacité w if poids[i-1] <= w: # On prend le max entre ne pas prendre l'objet et le prendre dp[i][w] = max(dp[i-1][w], valeurs[i-1] + dp[i-1][w - poids[i-1]]) else: # On ne peut pas prendre l'objet dp[i][w] = dp[i-1][w] return dp[n][W] # Exemple d'utilisation valeurs = [60, 100, 120] poids = [10, 20, 30] capacite = 50 print(sac_a_dos(capacite, poids, valeurs)) # Affiche 220
Cet algorithme a une complexité en O(n*W). Il illustre parfaitement comment la PD permet de construire progressivement la solution optimale.
Quand et pourquoi utiliser la programmation dynamique en NSI ?
La programmation dynamique n'est pas une solution universelle. Voici des signes qui peuvent t'indiquer qu'elle est adaptée :
- Le problème demande une valeur optimale (maximale, minimale, plus courte, etc.).
- Il peut être décomposé en étapes ou en sous-problèmes similaires.
- Une solution par force brute ou récursion naïve semble exploser exponentiellement.
- Tu reconnais des motifs de sous-problèmes qui se répètent.
En NSI, tu la rencontreras dans des contextes variés :
- Problèmes de plus court chemin (comme l'algorithme de Floyd-Warshall).
- Problèmes d'alignement de séquences (en bio-informatique).
- Jeux combinatoires simples.
- Découpe optimale (rod cutting).
- Le rendu de monnaie.
La maîtrise de la programmation dynamique demande de la pratique. Commence par bien analyser le problème, définir clairement ce que va stocker ton tableau (ou ton dictionnaire), et établir la relation de récurrence qui lie les sous-problèmes entre eux.
