动态规划，最小硬币数

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

我不明白为什么我们需要这个角色：

^{pr2}$

我试着用一个语句替换所有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的每个选项。在

^{pr2}$

循环中的下两行将跟踪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])