Dans une monnaie imaginaire, on dispose de pièces et de billets ayant
les valeurs suivantes :
[1, 2, 3, 7, 10, 20, 25]
Vous vous trouvez devant un distributeur et demandez une certaine somme donnée en entrée du problème. Sachant que l'automate dispose de toutes les valeurs de pièces mentionnées plus haut, en quantité suffisante, de combien de manières différentes peut-il vous donner la somme demandée ?
Par exemple, si la somme demandée était 10, elle pourrait être fournie de 18 façons différentes :
(10,) (3, 7) (1, 2, 7) (2, 2, 3, 3) (1, 3, 3, 3) (1, 1, 1, 7) (2, 2, 2, 2, 2) (1, 2, 2, 2, 3) (1, 1, 2, 3, 3) (1, 1, 2, 2, 2, 2) (1, 1, 1, 2, 2, 3) (1, 1, 1, 1, 3, 3) (1, 1, 1, 1, 2, 2, 2) (1, 1, 1, 1, 1, 2, 3) (1, 1, 1, 1, 1, 1, 2, 2) (1, 1, 1, 1, 1, 1, 1, 3) (1, 1, 1, 1, 1, 1, 1, 1, 2) (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)