Qu’est-ce qu’un sous-problème en programmation dynamique ?
Réponse courte
Un sous-problème est une version plus petite de la question initiale, de même nature, dont la réponse aide à construire la solution complète. La programmation dynamique mémorise ces réponses quand plusieurs calculs les réutilisent.
Comprendre
Une question de même nature
Un sous-problème réduit la taille de l’entrée tout en gardant le même objectif. Pour le rendu de monnaie, on cherche le nombre minimal de pièces pour différentes sommes. Si la cible est 6, connaître les minima pour 5, 3 ou 2 aide à évaluer le choix de la dernière pièce 1, 3 ou 4.
Construire la réponse
Avec les pièces 1, 3 et 4 disponibles sans limite, notons M(s) le minimum de pièces pour rendre s. La base est M(0) = 0. Pour une somme positive, essayer une pièce c qui ne dépasse pas s revient à ajouter une pièce au minimum de la somme restante s − c. Pour 6, les choix donnent 1 + M(5), 1 + M(3) et 1 + M(2) ; la meilleure réponse est 2, atteinte par 3 + 3.
Pourquoi mémoriser ?
Plusieurs choix peuvent faire réapparaître la même somme restante. Si elle est résolue plusieurs fois, le calcul se répète inutilement. Une table ou un dictionnaire garde sa réponse pour la réutiliser. L’état doit décrire suffisamment le sous-problème : si le stock de pièces devenait limité, la somme seule ne suffirait plus, car il faudrait aussi savoir quelles pièces restent.
Exemples
- Pour rendre 6 avec les pièces 1, 3 et 4, le choix final 3 laisse le sous-problème de somme 3 ; 3 + 3 donne deux pièces au total.
- Avec des pièces 1, 3, 4, M(0) = 0 ; M(3) = 1, car une pièce de valeur 3 suffit.
- Avec une seule pièce de 3 et une cible 6, le sous-problème doit aussi tenir compte du stock : réutiliser M(s) sans cette information autoriserait à tort deux fois la même pièce.
Pièges fréquents
- Appeler sous-problème n’importe quel calcul intermédiaire oublie qu’il doit répondre à une question de même nature et contribuer à la solution globale.
- Définir l’état seulement par la somme alors que le stock est limité entraîne une récurrence qui réutilise des pièces indisponibles.
Pourquoi ça marche
Une décomposition correcte rend une solution optimale dépendante de solutions optimales de cas plus petits, ce qui permet de les calculer une fois puis de les combiner.
