Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
La programmation dynamique (PD) résout un problème en combinant les solutions de ses sous-problèmes, dont on mémorise les résultats pour ne jamais les recalculer.
Un problème s'y prête s'il vérifie deux propriétés : - Sous-problèmes qui se recouvrent : les mêmes sous-calculs reviennent souvent (contrairement à diviser pour régner, où ils sont disjoints). - Sous-structure optimale : la solution optimale se construit à partir des solutions optimales des sous-problèmes.
Deux approches : - Descendante (top-down, mémoïsation) : récursion classique + mémoire des résultats déjà calculés. - Ascendante (bottom-up) : on remplit itérativement un tableau des petits sous-problèmes vers les grands.
L'exemple emblématique est Fibonacci : récursif naïf en O(2^n), mais O(n) avec PD.
Fibonacci itératif, O(n) temps et O(1) mémoire :
def fibo(n): if n < 2: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b
Rendu de monnaie (nombre minimal de pièces) :
def rendu_min(n, pieces): dp = [0] + [float('inf')] * n for montant in range(1, n + 1): for piece in pieces: if piece <= montant: dp[montant] = min(dp[montant], dp[montant - piece] + 1) return dp[n]
Relation : dp[m] = 1 + \min_{p \le m} dp[m - p], avec dp[0] = 0.
1. Vérifier les deux propriétés (recouvrement + sous-structure optimale).
2. Définir clairement le sous-problème (que représente dp[i] ?).
3. Écrire la relation de récurrence et les cas de base.
4. Choisir top-down (mémoïsation) ou bottom-up (tableau) et coder.
dp[0]) ou mal initialiser le tableau (utiliser float('inf') pour un minimum).dp[i] : toute la suite en dépend.Fibonacci (gain de la mémoïsation par rapport à la version naïve) et le rendu de monnaie sont les classiques attendus. Le correcteur attend que vous énonciez clairement la relation de récurrence et que vous identifiiez les deux propriétés (sous-problèmes se recouvrant, sous-structure optimale) qui distinguent la programmation dynamique de la simple méthode diviser pour régner. À l'épreuve pratique, on complète souvent un tableau dp : définissez d'abord précisément ce que représente dp[i], initialisez correctement (par exemple dp[0] et les valeurs neutres comme float('inf') pour un minimum), puis remplissez dans le bon ordre des petits sous-problèmes vers les grands. Pensez à comparer le coût exponentiel de la version récursive naïve au coût polynomial obtenu grâce à la mémorisation : c'est l'argument central qui motive tout le chapitre.