La programmation dynamique

Nommer exactement le sous-problème

Notons C(s) le nombre minimal de pièces nécessaires pour former la somme entière s, avec un stock illimité de chaque valeur autorisée. C(0)=0 : aucune pièce n’est nécessaire. Pour s positif, on essaie chaque dernière pièce p qui ne dépasse pas s, puis on considère 1+C(s-p).

La meilleure valeur est le minimum de ces possibilités. Si aucune combinaison ne forme s, on conserve un marqueur inaccessible. Cette définition de l’état est essentielle : C(s) ne représente ni la valeur des pièces choisies, ni une liste de solutions, mais un nombre minimal. Une table auxiliaire peut ensuite conserver un choix pour reconstruire une solution.

La récurrence est justifiée en retirant une dernière pièce d’une solution optimale. Le reste doit lui-même utiliser un nombre minimal de pièces pour sa somme : sinon on pourrait le remplacer par une meilleure solution et améliorer le total. Cette propriété explique pourquoi les sous-résultats suffisent à construire un optimum global.

Calculer dans l’ordre des dépendances

Avec les pièces 4,3,1, on obtient C(0)=0, C(1)=1, C(2)=2, C(3)=1, C(4)=1, C(5)=2 et C(6)=2. Pour six, les choix finaux donnent 1+C(2)=3 avec une pièce de quatre, 1+C(3)=2 avec une pièce de trois, ou 1+C(5)=3 avec une pièce de un.

Calculer de zéro vers la somme cible garantit que les résultats nécessaires existent déjà. La table rend visibles les dépendances et évite les appels répétés. Le calcul ne choisit pas seulement une pièce localement intéressante ; il compare des solutions complètes de sous-problèmes.

Mémoriser ou remplir un tableau

Une version récursive mémorisée conserve le résultat de chaque état à son premier calcul. Une version ascendante remplit directement le tableau dans l’ordre nécessaire. Les deux utilisent la même décomposition, mais organisent différemment le contrôle de l’exécution.

def minimum_pieces(somme, pieces):
    cout = [0] + [float("inf")] * somme
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s:
                cout[s] = min(cout[s], 1 + cout[s - p])
    return cout[somme]

Les préconditions sont une somme entière naturelle et des valeurs de pièces entières strictement positives. Sans positivité, les dépendances ne se dirigent plus nécessairement vers des sommes plus petites.

Réutiliser l’idée et compter les ressources

Pour une cible S et k valeurs de pièces, cette table examine au plus S×k possibilités et conserve S+1 coûts. La reconstruction demande aussi de mémoriser ou retrouver les choix optimaux. Une stratégie gloutonne peut être plus légère, mais ne garantit pas ici l’optimalité.

Un autre exemple est Fibonacci : F(n)=F(n-1)+F(n-2). La récursion naïve recalcule souvent les mêmes valeurs ; une table les réutilise. Si l’on veut seulement le dernier terme, deux valeurs précédentes suffisent et réduisent la mémoire. La bonne optimisation dépend de ce que l’on doit renvoyer : un coût seul, un résultat final ou une solution complète.

Exemple suivi : remplir puis reconstruire

Avec les pièces 4,3,1, calculons jusqu’à 8. Les coûts pour 0 à 8 sont 0,1,2,1,1,2,2,2,2. Pour 7, une dernière pièce 4 laisse 3, dont le coût vaut 1 : deux pièces suffisent. Une dernière pièce 3 laisse 4 et donne aussi deux. Pour 8, une dernière pièce 4 laisse 4 et donne encore deux pièces. Le minimum peut donc être obtenu par plusieurs choix, mais sa valeur est unique.

Pour reconstruire, stockons la pièce retenue lors d’une amélioration. Depuis 7, le choix 4 conduit au reste 3, puis le choix 3 conduit à zéro : [4,3] forme bien la somme et contient C(7)=2 pièces. La somme restante diminue strictement puisque les pièces sont positives. Conserver seulement le coût final ne donne pas immédiatement la composition ; il faut également les choix ou refaire une recherche parmi les transitions optimales.

Si la table choix contient pour chaque somme accessible une dernière pièce optimale, la reconstruction suivante accepte zéro et renvoie None pour une cible positive inaccessible. Elle suppose que le remplissage respecte les préconditions du cours.

def reconstruire(choix, somme):
    if somme > 0 and choix[somme] is None:
        return None
    rendu = []
    while somme > 0:
        piece = choix[somme]
        rendu.append(piece)
        somme -= piece
    return rendu

Exemple suivi : un glouton bloqué face à une solution existante

Avec les pièces 6 et 4, la table contient C(0)=0, C(4)=1, C(6)=1, C(8)=2, tandis que 1,2,3,5 et 7 sont inaccessibles. Pour 8, essayer une dernière pièce 6 laisse 2 inaccessible ; essayer 4 laisse 4 accessible en une pièce. La solution optimale est donc 4+4. Le glouton prend 6, laisse 2 et échoue, bien qu’une solution existe.

Le marqueur infini doit rester défavorable : 1+infini vaut encore infini dans ce modèle. Initialiser tous les coûts à zéro inventerait des solutions gratuites aux sommes impossibles. Les sommes impaires sont ici impossibles puisque chaque pièce est paire, mais toutes les sommes paires ne sont pas possibles : 2 est un contre-exemple. Utilisez la structure des données pour établir certaines impossibilités, puis la table pour vérifier précisément chaque cible.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Remplir les cases avant leurs dépendances.

Chaque état doit utiliser des sous-résultats déjà fiables.

Confondre minimum de coût et reconstruction de solution.

Un coût ne donne pas seul la liste des choix qui l’atteint.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Amérique du Nord · Jour 1 : Immeubles : SQL et plus longue sous-séquence croissante
• Bac 2026 · Antilles-Guyane · Jour 1 : Plus longue sous-séquence commune : de l’exhaustif au dynamique
• Bac 2026 · Antilles-Guyane · Jour 2 : Scierie : valoriser le stock et optimiser les découpes
• Bac 2026 · Polynésie · Jour 1 : Fibonacci : mesurer le prix des calculs répétés

Le prochain pas

• Coûts en temps et en mémoire

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.