递归：用最少的硬币进行更改

Question

我正在用python研究数据结构和算法。这是一个经典的递归问题，涉及到用最少的硬币进行更改。这是密码。 我不明白的是第二行。为什么我们需要minCoins = change？8-9号线是什么意思？有人能解释一下吗？非常感谢你的帮助！在

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

Answer 1

^{cd1>}：^{{cd2>}初始化时，值为^{{cd3>}，这是^{{cd4>}可以返回的最大值，因为硬币的最小值为1，假设硬币的整数值。

^{cd5>}:base case 1-如果某个硬币的值为^{{cd3>}的值，我们只需要抓住这1枚硬币，从而返回1

for i in [c for c in coinValueList if c <= change]:： 然后，函数将1个硬币的所有可能值循环到

从^{{cd3>}中扣除硬币值^{cd9>}，将1枚硬币添加到所需的硬币数量，这些硬币是为剩余变化递归计算的（^{cd11>}）。这是从2基础病例中归纳出来的

在这个循环中，{cd12>}有效地分配了可能的最小数量的硬币^{{cd2>}

如果^{cd3>}的初始化值仍然为^{cd2>}（表示^{cd17>}中没有值^{{cd16>}），这意味着所需的硬币数量也是^{cd3>}，即^{cd3>}1-单位硬币的值。这是基于一个值为1的硬币始终可用的前提条件的基础情况2。