Набор данных для проверки задачи:
Количество монет в наборе: 3
Набор возможных монет: [1, 5, 10]
Сумма, которую требуется разменять: 8
Шаги решения:
1. Создать массив dp размером sum+1, где sum – сумма, которую требуется разменять.
2. Инициализировать все элементы массива dp значением “бесконечность” (INF), кроме элемента dp[0], который устанавливаем равным 0.
3. Пройти по каждой монете coin в наборе возможных монет.
4. Внутри цикла пройти по каждому числу i от coin до sum.
5. Внутри цикла если dp[i-coin] != INF (это означает, что размен суммы i-coin возможен), то обновляем dp[i] как минимальное значение между dp[i] и dp[i-coin]+1.
6. В конце вернуть значение dp[sum].
В случае с данным набором данных программа, написанная динамическим способом, должна вернуть значение “бесконечность” (INF), так как данный набор монет не позволяет разменять сумму 8.