动态规划最优硬币更换

Question

我一直在复习一些动态编程问题，在寻找最小数量的硬币来进行更改方面，我很难把自己的脑袋放在一些代码上。

假设我们有价值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 <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

如果有人能帮我理解这段代码（第4行是我开始感到困惑的地方），那就太好了。谢谢！

Answer 1

我认为第四行很混乱，因为虽然Python可以在列表理解中选择/过滤，但在其标准表达式中却不能这样做。

所以人们的一种方式就是把两者结合在一起。它们创建了一个列表理解，实际上它没有转换（因此是c for c in coinValueList），只是为了添加if c <= cents子句。然后将其用作标准for x in iterable:表达式的iterable。我想这就是你困惑的原因。

另一种写法可能是：

...
for eachCoinValue in filter(lambda x: x <= cents, coinValueList):
...

或者更清楚地说，“意图揭示变量”是：

...
smallEnoughCoins = filter(lambda each: each <= cents)
for each in smallEnoughCoins:
    ...