Решение динамического программирования не подходит для решения проблемы внесения изменений? ⇐ Python

[Anonymous]

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

Код: Выделить всё

def count_change(denoms, denoms_length, amount):
"""
Finds the number of ways that the given number of cents can be represented.
:param denoms: Values of the coins available
:param denoms_length: Number of denoms
:param amount: Given cent
:return: The number of ways that the given number of cents can be represented.
"""

# Write your code here!
return helper(denoms, amount)

def helper(denoms, amount, i=0):
if amount == 0:
return 1
elif i >= len(denoms):
return 0
else:
count = 0
coin = denoms[i]
if coin < amount:
mult = amount // coin
for m in range(1, mult+1):
count += helper(denoms, amount - (coin*m), i+1)
else:
count += helper(denoms, amount, i+1)

return count

count_change([25, 10, 5, 1], 4, 30)
>>> 1 #should be 18

Эта проблема связана с платным доступом, поэтому я не могу установить ссылку. Больше всего меня сбивает с толку то, что у монеты есть несколько кратных, меньших суммы. В этом суть цикла for в предложении else.
Что я здесь делаю не так?

Подробнее здесь: https://stackoverflow.com/questions/736 ... ng-problem