Задача про кассира-программиста

Задача, которую давали на собеседованиях в Apple. Представьте, что вы получили работу кассира в магазине. Ваш босс случайно выяснил, что вы обладаете навыками программиста, и захотел, чтобы вы помогли ему написать программу.

Входные данные:

1. Указанная сумма денег.
2. Массив со всеми доступными номиналами монет.

Нужно написать функцию, которая на выходе выдаст количество всех возможных способов получить указанную сумму денег при помощи различных доступных номиналов монет. Например, если вам нужно получить 4 цента из монет номиналами 1, 2 и 3 цента, то функция вернет 4 — именно столько есть возможных комбинаций из чисел 1, 2 и 3, чтобы получить в сумме 4:

1. 1, 1, 1, 1.
2. 1, 1, 2.
3. 1, 3.
4. 2, 2.

Решение

Мы используем динамическое программирование, чтобы создать массив ways_of_doing_n_cents таким образом, что ways_of_doing_n_cents[k] содержит значение количества способов собрать сумму k, используя доступные номиналы. Для начала мы начнем с отсутствия номиналов, имея лишь один вариант — собрать сумму 0, затем мы будем добавлять по одному номиналу, по возрастанию, и одновременно редактировать наш массив с учетом новых номиналов.

Количество новых вариантов, которыми мы можем сделать сумму higher_amount с учетом нового номинала монеты coin, вычисляется как уже существующее значение ways_of_doing_n_cents[higher_amount - coin]. Нам уже известны все комбинации с предыдущими номиналами, поэтому мы используем эту информацию при добавлении нового номинала. При добавлении первого номинала, мы считаем, что предыдущий номинал равен 0.

Код решения на Python:

			def change_possibilities_bottom_up(amount, denominations):
    ways_of_doing_n_cents = [0] * (amount + 1)
    ways_of_doing_n_cents[0] = 1

    for coin in denominations:
        for higher_amount in xrange(coin, amount + 1):
            higher_amount_remainder = higher_amount - coin
            ways_of_doing_n_cents[higher_amount] += ways_of_doing_n_cents[higher_amount_remainder]

    return ways_of_doing_n_cents[amount]
		

Чтобы было понятнее, вот что содержит массив ways_of_doing_n_cents по мере выполнения итераций, при этом сумма равна 5 и номиналы равны 1, 3 и 5:

			===========
key:
a = higher_amount
r = higher_amount_remainder
===========

============
for coin = 1:
============
[1, 1, 0, 0, 0, 0]
 r  a

[1, 1, 1, 0, 0, 0]
    r  a

[1, 1, 1, 1, 0, 0]
       r  a

[1, 1, 1, 1, 1, 0]
          r  a

[1, 1, 1, 1, 1, 1]
             r  a

============
for coin = 3:
=============
[1, 1, 1, 2, 1, 1]
 r        a

[1, 1, 1, 2, 2, 1]
    r        a

[1, 1, 1, 2, 2, 2]
       r        a

============
for coin = 5:
=============
[1, 1, 1, 2, 2, 3]
 r              a


final answer: 3
		

Сложность алгоритма — O(n*m) по времени и O(n) по памяти, где n — это сумма, а m — количество различных номиналов.

Источник: Interview Cake