Задача динамического программирования на монетах

Рассмотрим следующую задачу

Дано бесконечное число пятаков (5 центов) и Пенни(1 цент). Напишите код для вычисления количества способов представления n центов.

Мой код 

def coins(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    else:
        if (cnt_lst[n-1] == 0):
            cnt_lst[n-1] = coins(n-1) + coins(n-5)
        return cnt_lst[n-1]

if __name__ == "__main__":
    cnt = int(input())
    cnt_lst = [0] * cnt #Memiozation
    ret = coins(cnt)
    print(ret)

Выше оценочность подсчета повторяющихся паттернов более одного (очевидно, я не проверяю их явно).

[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc

Ведение другого списка, содержащего ранее замеченные паттерны, потребует много памяти по мере роста n. Какой еще подход мы можем использовать для преодоления этой проблемы?

2 4
python recursion memoization dynamic-programming

2 ответа:

Вместо использования одномерного списка можно использовать двумерный массив, где одно измерение-это сумма, а второе измерение-самая крупная монета из доступных.

Предположим, что C - это ваш список значений монет в порядке возрастания (в вашем примере C = [1, 5]). Тогда пусть A[i][j] - это число способов представления ценности i с помощью монет 0 через j.

Мы знаем, что для любого j, A[0][j] = 1 потому что существует ровно один способ представления значения 0: нет монеты.

Теперь предположим, что мы хотим найти A[8][1], число способов представляет собой 8 центов с Пенни и пятаками. Каждое представление будет либо использовать никель, либо нет. если мы не используем никель, то мы можем использовать только Пенни, поэтому есть A[8][0] способы сделать это. Если мы используем никель, то у нас остается 3 центов, поэтому есть A[3][1] способов сделать это.

Для вычисления A[8][0] у нас есть только одна монета, так что A[8][0] = A[7][0] = ... = A[0][0] = 1.

Для вычисления A[3][1] мы не можем использовать никель, так как 3 < 5, так что A[3][1] = A[3][0]. Оттуда мы имеем A[3][0] = A[2][0] = ... = 1, как и выше.

В целом: 

A[i][j] = A[i][j-1] if i < C[j]
          else A[i][j-1] + A[i-C[j]][j]
Этот алгоритм работает для любого набора значений монет.
2

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

Я думаю, что решение просто floor(N/5) + 1

Поскольку вы можете использовать только [0..N/5] 5 центов, остальные оставшиеся вы должны использовать 1 цент

Это может быть сделано, что легко, потому что ваша система монет каноническая и жадный алгоритм / мышление может быть прикладная.

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

Определить C(x, m):= The # of ways to make number x using first m type of coins

Итак, теперь рекуррентная формула становится:

C(x, m) = C(x-coin_type[m], m) + C(x, m-1), означает, что вы выбираете использовать монету m-го типа или не использовать ее

Вот главный момент, почему этот рекуррент работает, а ваш не работает, это порядок итерации государство.

Используя эту рекуррентную формулу, мы можем сделать что-то вроде 

For i = 0 to # of coin_type
    For j = 0 to n
       C(j, i) = C(j-coin_type[i], i) + C(j, i-1)
Обратите внимание, что внешний цикл заставляет упорядочивать итерации типа монет. Скажем coin_type = {1,3,5}, цикл сначала будет считать способ использования только {1}, затем следующая итерация цикла будет считать способ использования {1,3}, последняя итерация будет считать способ использования {1,3,5}.

Вы никогда не будете считать путь, используя {3,1,5}, или {1,5,3}...и т.д. Порядок типа монеты фиксирован, то есть вы не будете двойной рассчитывать, что

2