Programmation dynamique
La programmation dynamique résout une seule fois les sous-problèmes, conserve leurs réponses et les réutilise au lieu de refaire le travail. Un état contient les informations nécessaires pour définir un sous-problème ; une récurrence indique comment calculer sa réponse à partir d’autres états. Dans les formulations présentées ici, ces dépendances forment un graphe orienté acyclique : les suivre ne doit pas ramener à un état encore en cours de calcul. La mémoïsation calcule et mémorise les réponses à la demande des appels récursifs ; la tabulation suit un ordre prévu, en calculant les dépendances d’abord. La difficulté principale consiste à déterminer ce que chaque état doit retenir et pourquoi la récurrence couvre tous les choix valides.
Liste de contrôle pour la conception
- État : quelle information minimale rend le problème restant indépendant du chemin suivi pour atteindre cet état ?
- Valeur : que signifie
dp[state]— faisabilité, nombre, coût minimal, valeur maximale ou solution concrète ? - Transition : quels états plus petits peuvent produire cet état ?
- Cas de base : quels sont les plus petits sous-problèmes valides ?
- Ordre : chaque dépendance existe-t-elle avant d'être lue ?
- Réponse : quel état ou agrégat contient le résultat demandé ?
Approche descendante ou ascendante
Le nombre d'états multiplié par le travail de chaque transition donne une première estimation de la complexité. On ne peut compresser la mémoire que si les états écrasés ne seront plus nécessaires aux transitions futures ni à la reconstruction.
Schéma de preuve
Prouvez d'abord que l'état conserve tout l'historique pertinent, puis raisonnez par induction selon l'ordre des dépendances : si les états plus petits sont corrects, la récurrence examine chaque dernier choix valide et les sélectionne ou les combine conformément à l'objectif.
Quand la programmation dynamique ne convient pas
Elle n'est guère utile si l'état choisi dépend encore d'un historique non borné, si l'espace des états dépasse la recherche directe ou si une propriété gloutonne ou d'échange évite de comparer les possibilités. Enrichir l'état peut rétablir la correction, mais rendre l'algorithme impraticable.
Concevoir un état : nombre minimal de pièces
Avec les dénominations entières positives [1,3,4] disponibles sans limite, prendre d'abord la plus grande donne 4+1+1 pour 6, soit trois pièces, contre deux avec 3+3. Ce contre-exemple réfute la règle gloutonne ; le chevauchement des sous-problèmes ne suffit pas à prouver une nouvelle récurrence.
Définissez dp[t] comme le nombre minimal de pièces totalisant exactement t. Posez dp[0]=0 ; un montant impossible commence à l'infini, pas à zéro. Pour t positif, essayez chaque pièce c ne dépassant pas t et minimisez 1+dp[t-c]. Toute solution possède une dernière pièce ; la retirer laisse exactement le montant plus petit annoncé, donc les choix sont exhaustifs. Des dénominations positives assurent des dépendances strictement plus petites. Pour les montants 0 à 6, on obtient [0,1,2,1,1,2,2]. Le temps est O(Tk) et l'espace O(T), pour une cible T et k dénominations. Avec [4] et une cible 6, le montant est inaccessible.
def min_coins(coins, target):
if target < 0 or any(c <= 0 for c in coins):
raise ValueError("positive denominations and nonnegative target required")
dp = [0] + [float("inf")] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount:
dp[amount] = min(dp[amount], 1 + dp[amount - coin])
return dp[target]
assert min_coins([1, 3, 4], 6) == 2
assert min_coins([4], 6) == float("inf")
assert min_coins([], 0) == 0
Ce que chaque état doit retenir
Fibonacci part d’un indice et de valeurs antérieures réutilisables. Le sac à dos 0/1 ajoute la disponibilité des objets et la capacité ; la plus longue sous-séquence commune utilise deux longueurs de préfixe. Les plus courts chemins par programmation dynamique expliquent quel ordre du graphe rend les dépendances acycliques. La différence porte sur l’information mémorisée, pas sur la présence d’un tableau.