Динамическое программирование: размен денег

Это запись -  пример выгодного использование рекурсии. Тем, кто еще не ознакомился, советую прочитать - Линейные рекурсия и итерация. Чего не хватает Python. Я считаю, что именно в тематике динамического программирования рекурсия побеждает всех, как говорится "в шлемах и без" :) Тут я хочу рассмотреть всем известную(а может и не всем, раз вы читаете) задачу размена денег. У неё есть несколько интерпретаций, таких как:

1. Как дать сдачу определенной суммы, определенным набором монет
2. Сколькими способами конь может дойти до определенного места на шахмотной доске.
3. И др.....

*-Нравится статья? Кликни по рекламе! :)
Чтобы сочинить итеративный алгоритм для чисел Фибоначчи, нужно совсем немного смекалки. Теперь для контраста рассмотрим следующую задачу:

Сколькими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент?

В более общем случае, можно ли написать процедуру подсчета способов размена для произвольной суммы денег? У этой задачи есть простое решение в виде рекурсивной процедуры. Предположим, мы как-то упорядочили типы монет, которые у нас есть. В таком случае верно будет
следующее уравнение:

Число способов разменять сумму a с помощью n типов монет равняется

• числу способов разменять сумму a с помощью всех типов монет, кроме первого,плюс
• число способов разменять сумму a − d с использованием всех n типов монет, где d — достоинство монет первого типа.

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

• Если a в точности равно 0, мы считаем, что имеем 1 способ размена.
• Если a меньше 0, мы считаем, что имеем 0 способов размена.
• Если n равно 0, мы считаем, что имеем 0 способов размена.

Это описание легко перевести в рекурсивную процедуру:

def countChange(amount):
    return cc(amount, 5)

def cc(amount, kindsOfCoins):
    if amount==0:
        return 1
    if amount<0 or kindsOfCoins==0:
        return 0
    else:
        return cc(amount, kindsOfCoins-1)+cc(amount-firstDenomination(kindsOfCoins), kindsOfCoins)

def firstDenomination(kindsOfCoins):
    if kindsOfCoins==1:
        return 1#1 цент
    elif kindsOfCoins==2:
        return 5#5 центов
    elif kindsOfCoins==3:
        return 10#10 центов
    elif kindsOfCoins==4:
        return 25#25 центов
    else:
        return 50#50 центов

Процедура firstDenomination принимает в качестве входа число доступных типов монет и возвращает достоинство первого типа. Здесь мы упорядочили монеты от самой крупной к более мелким, но годился бы и любой другой порядок.
Проверим countChange(100) - выдает нам 292 комбинации размена 100 центов.
Используемая литература:

1. http://mitpress.mit.edu/sicp/