动态规划最优硬币更换

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:
    ...

Answer 2

如果你熟悉图论的话，这里有一种思考硬币兑换问题的方法，这可能是有用的。

假设您有一个按以下方式定义的图：

• 从0到您感兴趣的价值（如39美分或其他），每单位货币（如便士）有一个节点
• 任何两个节点之间都有一个弧，由允许使用的硬币的值隔开（例如，如果允许使用镍币，则一个介于34美分和29美分之间的节点）

现在你可以把换硬币的问题看作是一个从你的兴趣值降到零的最短路径问题，因为硬币的数量将与你路径中的弧的数量完全相同。

该算法不使用图论术语，但它做的基本上是相同的事情：外循环覆盖所有“分”（或节点，在图论框架中）和内循环覆盖从当前弧到下一个弧的所有弧（coinValueList中的值）。总之，他们在寻找从零到你感兴趣的价值的最短路径。（价值降到零，零升到价值，都无关紧要。不过，传统上我们会向下搜索到零。）

当我意识到许多问题可以被转化为图问题时，我才真正开始理解动态编程。（不过，要小心——不是所有人都能。有些是超图，有些甚至可能不是超图。但这对我帮助很大。）

Answer 3

在我看来，代码正在解决每一分钱到目标分钱的问题。给定目标值v和一组硬币C，您知道最佳硬币选择S必须是union(S', c)形式，其中c是来自C的一些硬币，而S'是v - value(c)的最佳解决方案（请原谅我的注释）。所以问题是optimal substructure。动态规划方法是解决每一个可能的子问题。它需要cents * size(C)步骤，而不是那些如果你试图强行直接解决的话会爆炸得更快的东西。

def dpMakeChange(coinValueList,change,minCoins):
   # Solve the problem for each number of cents less than the target
   for cents in range(change+1):

      # At worst, it takes all pennies, so make that the base solution
      coinCount = cents

      # Try all coin values less than the current number of cents
      for j in [c for c in coinValueList if c <= cents]:

            # See if a solution to current number of cents minus the value
            # of the current coin, with one more coin added is the best 
            # solution so far  
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1

      # Memoize the solution for the current number of cents
      minCoins[cents] = coinCount

   # By the time we're here, we've built the solution to the overall problem, 
   # so return it
   return minCoins[change]