Programmer dynamiquement

Un sous-problème est une question de même nature que la question initiale, mais portant sur une entrée plus petite. Dans le rendu de monnaie, connaître le minimum de pièces pour la somme s aide à résoudre certaines sommes plus grandes. La programmation dynamique devient utile lorsque les mêmes sous-problèmes réapparaissent dans plusieurs branches de calcul. Les résoudre une fois, puis réutiliser leurs réponses, évite cette répétition.

Prenons des pièces de valeurs 1, 3 et 4. Pour rendre 6, une stratégie gloutonne choisit d’abord 4, puis 1, puis 1 : elle utilise trois pièces. Pourtant 3 + 3 utilise seulement deux pièces. Un choix local qui paraît favorable ne garantit donc pas une solution globalement optimale. Cet exemple ne dit pas que toute méthode gloutonne échoue toujours ; il montre qu’il faut justifier sa validité pour le système de pièces étudié.

Deux propriétés guident la méthode. D’abord, les solutions recherchées se décrivent à partir de solutions de sous-problèmes. Ensuite, les sous-problèmes se recouvrent : la même somme restante peut apparaître après différents choix. La première propriété permet d’écrire une relation de récurrence ; la seconde explique l’intérêt de mémoriser. Une récursion qui recalcule sans cesse les mêmes valeurs ne tire pas encore parti de cette mémorisation.

Notons M(s) le nombre minimal de pièces nécessaires pour rendre exactement la somme s. Pour s = 0, aucune pièce n’est nécessaire : M(0) = 0. Pour une somme positive, on envisage chaque valeur c disponible telle que c ≤ s. Si c est la dernière pièce choisie, il reste s − c à rendre. Le nombre de pièces correspondant est donc 1 + M(s − c). On choisit le minimum de ces candidats.

La relation s’écrit M(s) = 1 + min des M(s − c), pour les pièces c qui ne dépassent pas s et dont le reste est réalisable. Le terme 1 compte la pièce ajoutée. Avec une pièce de valeur 1, toutes les sommes entières positives sont réalisables. Sans cette pièce, certaines sommes peuvent être impossibles ; il faut alors utiliser une valeur spéciale représentant l’impossibilité, et non la confondre avec zéro.

Pourquoi peut-on utiliser une solution optimale du reste ? Si une solution minimale pour s terminée par c contenait une façon non optimale de rendre s − c, on pourrait remplacer cette partie par une meilleure et diminuer le nombre total de pièces. Cela contredirait la minimalité supposée. Ce raisonnement justifie la relation ; recopier une formule sans expliquer le rôle de l’état ne suffit pas.

La table des minimums indique une quantité, mais pas directement la combinaison choisie. Un second tableau, dernier, peut mémoriser une pièce atteignant le minimum de chaque somme. Pour reconstruire, partir de S, lire dernier[S], soustraire cette pièce, puis recommencer jusqu’à zéro. La somme diminue strictement puisque toutes les pièces sont positives ; la reconstruction termine donc si la somme initiale est réalisable.

On peut également partir d’une fonction récursive qui calcule M(s) en demandant les valeurs des restes. Avant tout nouveau calcul, elle consulte un dictionnaire de résultats déjà connus. Si la valeur existe, elle la renvoie ; sinon, elle la calcule puis l’enregistre. Cette méthode descendante est appelée mémoïsation. Le remplissage progressif du tableau est une méthode ascendante. Les deux approches utilisent la même relation, mais n’organisent pas le travail de la même façon.

Avec k valeurs de pièces et une cible S, un remplissage ascendant examine au plus k possibilités pour chacune des S sommes positives. Son coût est O(kS), en comptant les opérations arithmétiques et les accès usuels comme élémentaires. Les tableaux occupent O(S) cases. Cette borne dépend de la valeur numérique de S : doubler une somme très grande peut coûter cher même si son écriture n’ajoute qu’un chiffre.

L’ordre du calcul compte. La case M(s) dépend de sommes strictement inférieures à s, donc elles doivent déjà être connues. Remplir le tableau dans l’ordre décroissant échouerait avec cette relation. De même, une pièce nulle ferait dépendre M(s) de lui-même et une pièce négative pourrait renvoyer vers une somme supérieure. Le contrat impose des pièces strictement positives ; ce n’est pas un détail de présentation.

Pour tester une implémentation, vérifier la somme zéro, une somme égale à une pièce, une somme impossible et un cas où le glouton échoue. Pour une combinaison renvoyée, contrôler que chaque valeur est autorisée, que la somme est exacte et que le nombre de pièces correspond au minimum. Sur de petites sommes, une exploration exhaustive indépendante permet de comparer les résultats et de révéler une erreur de récurrence ou d’initialisation.

Pour poursuivre ton entraînement, ouvre la rubrique S’entraîner du site, à l’adresse /exercices. Reprends d’abord les questions de cette leçon sans afficher les réponses, puis compare ton raisonnement à la correction.