Напишите на Python программу, которая определяет, сколько различных способов можно выдать сдачу в заданной сумме

Тема: Подсчет различных способов выдачи сдачи в заданной сумме

Пояснение: Программа, которая определяет количество различных способов выдачи сдачи в заданной сумме, может быть написана с использованием динамического программирования. Мы можем решить эту задачу, используя только один цикл while.

Суть алгоритма состоит в том, чтобы создать массив dp, в котором каждый элемент будет содержать количество различных способов получения сдачи для данной суммы. Затем мы будем обновлять значения dp для каждой суммы от 1 до n, используя уже вычисленные значения. Начальное значение dp[0] будет равно 1, так как у нас всегда есть один способ получить сдачу равную 0.

Для каждого номинала монеты, меньшего или равного текущей сумме, мы будем увеличивать значения dp соответствующим образом. Например, для суммы в 5 рублей, у нас есть 4 различных варианта выдачи: 5x1, 2x2+1x1, 1x2+3x1 и 5x1.

Пример использования:
Входные данные: 5
Вывод: 4

Совет: Чтобы лучше понять алгоритм, вы можете вручную пройтись по нескольким примерам и посчитать количество различных способов выдачи. Это поможет вам лучше понять логику и проверить правильность реализации программы.

Упражнение: Напишите программу на Python, которая будет определять количество различных способов выдачи сдачи для заданной суммы входных данных.