Решение динамического программирования неуместно для проблем с принятием изменений? ⇐ 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
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
< /code>
Эта проблема стоит за платным положением, поэтому я не могу связать. Часть, которая меня наиболее сбивает с толку, - это когда монета имеет несколько кратных, которые меньше, чем количество. Это дух, стоящий за петлей в предложении Else.
Что я здесь делаю?

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