[C++] program obliczający na ile sposobów można rozmienić kwotę

Witam,

mam taką zagadkę logiczną, której nie umiem rozgryźć.

Staram się napisać program który wczytuje pewną kwotę złotych i groszy np. 127zł i 67gr i jako wynik wyświetla informacje na ile sposobów można rozmienić tą kwotę używając wszystkich dostępnych nominałów(5zł, 2zł, 1zł, 50gr, 20gr, 10gr, 5gr, 2gr, 1gr).

Prawdopodobnie nie da się tego zrobić bez użycia symbolu Newtona, oraz liczby Calatana. Pogubiłem się, jestem słaby z logiki, wszelkie sugestie będą mile widziane :slight_smile:

Sugeruje innym użytkownikom forum nie podawać rozwiązań wprost, gdyż jest to kopia zadania: http://pl.spoj.com/problems/AL_02_01/
 

@maksior5
Hint. Programowanie dynamiczne.