Монетообменик. Решение задачи.

Приведенное ниже решение использует динамическое программирование снизу-вверх.

В этом поможет массив, в котором хранятся значения заведомо большие целевого (необходимо для корректной работы алгоритма), а далее для каждого значения в промежутке от 0 до значения amount, осуществляется расчет минимального количества монет, которыми можно получить данное число путем перебора всевозможных комбинаций монет.