Оптимизация решения для внесения изменений ⇐ Python

[Anonymous]

Здесь я написал решение на Python, которое решает следующую проблему: как можно получить заданную сумму денег n с наименьшим количеством монет данного номинала d?

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

def min_coin_change(n, d):
mini = float("inf")
for den in d:
diff = n - den
if diff == 0:
ans = 1
elif diff < 0:
ans = float("inf")
else:
ans = 1 + min_coin_change(n - den, d)
mini = min(mini, ans)
return mini

Хотя мое решение работает, оно занимает очень много времени, когда n больше 50 или когда длина d больше 5 Как я могу ускорить свой код, чтобы он работал со значительно большими входными данными? Я упускаю какой-то трюк или что-то, что могло бы значительно ускорить мой код?

Подробнее здесь: https://stackoverflow.com/questions/220 ... g-solution