Pourquoi mémoriser les résultats en programmation dynamique ?
Réponse courte
Mémoriser les résultats en programmation dynamique évite de recalculer plusieurs fois un même sous-problème. On conserve sa réponse dans un tableau ou un dictionnaire, puis on la réutilise lorsqu’un autre choix mène au même état.
Comprendre
Repérer les calculs qui se recouvrent
Dans une décomposition récursive, des branches différentes peuvent demander la réponse à la même question réduite. Pour le rendu de monnaie, plusieurs façons d’essayer la dernière pièce peuvent conduire à calculer le minimum d’une même somme restante. Sans mémoire, une récursion peut répéter ce travail.
Enregistrer puis réutiliser
Une méthode descendante consulte d’abord un dictionnaire : si M(s) est déjà connu, elle renvoie cette valeur ; sinon elle le calcule et l’enregistre. C’est la mémoïsation. Une méthode ascendante remplit plutôt un tableau des sommes dans un ordre où les sous-résultats nécessaires sont déjà disponibles. Les deux méthodes s’appuient sur la même relation entre états.
Mémoriser une réponse n’est pas toujours mémoriser le choix
Pour les pièces 1, 3 et 4, le tableau des minima jusqu’à 6 vaut [0, 1, 2, 1, 1, 2, 2]. Il donne M(6) = 2, mais pas à lui seul les pièces choisies. Pour reconstruire une combinaison, on peut aussi stocker une pièce qui atteint chaque minimum ; les choix 3 pour 6 puis 3 pour 3 produisent [3, 3]. La mémoire évite les calculs redondants, pas la nécessité de définir correctement l’état et les cas de base.
Exemples
- Pour les pièces 1, 3, 4, la table des minima jusqu’à la somme 6 est [0, 1, 2, 1, 1, 2, 2] ; la valeur M(3) est conservée pour les calculs ultérieurs.
- Si une fonction récursive redemande M(3), un dictionnaire contenant déjà cette clé permet de renvoyer la réponse sans recalculer les sommes inférieures.
- Conserver seulement M(6) = 2 donne le nombre minimal de pièces, mais pas directement la combinaison ; mémoriser le choix effectué permet de reconstruire 3 + 3.
Pièges fréquents
- Ajouter un tableau sans le consulter avant chaque calcul ne supprime aucun recalcul : il faut lire la valeur mémorisée quand l’état a déjà été résolu.
- Croire que le nombre minimal de pièces suffit toujours à produire la combinaison oublie qu’il faut enregistrer aussi un choix optimal si on veut reconstruire la solution.
Pourquoi ça marche
Quand plusieurs branches partagent un même état, une réponse calculée une fois reste valable pour chacune d’elles et peut être réutilisée.
