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

Скажем, у нас есть монеты достоинством 25, 10 и 1, и мы вносим изменения в 30. Жадность вернула бы 25 и 5 (1), в то время как оптимальное решение вернуло бы 3 (10). Вот код из книги по этой проблеме:

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c