Динамическое программирование, минимальное количество монет

Question

Я изучал алгоритмы и структуры данных на https://runestone.academy/runestone/static/pythonds/index.html, и я подошел к части о динамическом программировании и классической проблеме минимального количества монет. Учитывая сумму, мы должны выяснить, какое минимальное количество монет требуется, чтобы поменять ее на монеты разных номиналов.

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

Код здесь:

def recMC(coinValueList,change):
   minCoins = change
   if change in coinValueList:
     return 1
   else:
      for i in [c for c in coinValueList if c <= change]:
         numCoins = 1 + recMC(coinValueList,change-i)
         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

print(recMC([1,5,10,25],63))

и я не понимаю, зачем нам эта часть:

         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

Я попытался заменить все 3 строки одним утверждением

   return numCoins 

И, кажется, работает нормально, за исключением случаев, когда change == 0, Я не думаю, что способ, которым они написали это в книге, предназначен для "защиты" от ввода 0, поскольку это может быть обработано еще более тривиально.

Почему они написали так, как сделали?

PS: я запускаю его на python3.5, если это имеет значение...

ура

Answer 1

Как объяснено в главе,

Если сумма не совпадает, у нас есть несколько вариантов. То, что мы хотим, это минимум копейки плюс количество монет, необходимое для внесения изменений в исходную сумму минус пенни, или никель плюс количество монет, необходимых для внесения изменений в исходную сумму минус пять центов, или десять центов плюс количество монет, необходимое для внесения изменений в исходную сумму минус десять центов и т. д. Таким образом, количество монет, необходимых для внесения изменений в исходную сумму, можно рассчитать по следующей формуле:

numCoins=min(1+numCoins(originalamount−1),
             1+numCoins(originalamount−5),
             1+numCoins(originalamount−10),
             1+numCoins(originalamount−25))

Нижняя строка цикла for вычисляет каждый из параметров для numCoins.

for i in [c for c in coinValueList if c <= change]:
     numCoins = 1 + recMC(coinValueList,change-i)

Следующие две строки в цикле отслеживают минимальное значение numCoins:

if numCoins < minCoins:
        minCoins = numCoins

Чтобы упростить отслеживание, вы можете переписать функцию следующим образом:

def recMC(coinValueList,change):
    if change in coinValueList:
        return 1
    else:
        return min([1 + recMC(coinValueList,change-c) for c in coinValueList if c < change])