python - 动态规划，最小硬币数量

Question

我一直在研究算法和数据结构https://runestone.academy/runestone/static/pythonds/index.html ，然后我进入了关于动态规划和经典的最小硬币数量问题的部分。给定一个金额，我们必须计算出将其兑换成不同面额的硬币所需的最少数量的硬币。

在本书提出解决问题的代码中，有两行代码我无法弄清楚它们的作用，即使我的生命依赖于它们。

代码在这里:

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

如 chapter 中所述,

If the amount does not match we have several options. What we want is the minimum of a penny plus the number of coins needed to make change for the original amount minus a penny, or a nickel plus the number of coins needed to make change for the original amount minus five cents, or a dime plus the number of coins needed to make change for the original amount minus ten cents, and so on. So the number of coins needed to make change for the original amount can be computed according to the following:

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])