我一直在审查一些动态编程问题，我很难在一些代码中找到最小数量的硬币来进行更改。
假设我们有价值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行是我开始感到困惑的地方)，那就太好了。谢谢
在我看来，代码正在解决直到目标分值的每个分值的问题。给定目标值v和一组硬币C，您知道最佳硬币选择S必须为union(S', c)的形式，其中c是来自C的一些硬币，而S'是v - value(c)的最佳解(请原谅我的注释)。因此问题具有最优子结构。动态规划方法是解决每一个可能的子问题。它需要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]
如果你熟悉图论，这里有一种思考硬币兑换问题的方法，可能会很有用。
假设您有一个以以下方式定义的图：
- 从0到您感兴趣的价值(例如39美分或其他)，每单位货币(例如便士)都有一个节点
- 任何两个节点之间都有一条弧，由允许使用的硬币的价值分隔(例如，如果允许使用五分硬币，则为34美分至29美分之间的节点)
现在你可以把换币问题看作是从你感兴趣的值降到零的最短路径问题，因为硬币的数量与你路径中的弧的数量完全相同。
该算法没有使用图论术语，但它做的基本上是一样的：外循环在所有"美分"(或节点，在图论框架中)上进行，内循环在从当前弧到下一弧的所有弧(coinValueList中的值)上进行，他们正在寻找从零到你感兴趣的价值的最短路径。(值降到零，零升到值，都没关系。不过，传统上我们会向下搜索到零。)
当我意识到许多问题可以归结为图问题时，我才真正开始理解动态编程。(不过要小心——并不是所有的都能。有些是超图，有些甚至可能不是超图。但这对我帮助很大。)
我认为第四行令人困惑，因为虽然Python可以在列表理解(transform(x) for x in iterable if condition(x))中选择/筛选，但在标准for x in iterable:表达式中却不能这样做。
因此，人们四处走动的一种方式是将两者焊接在一起。他们创建了一个实际上不进行转换的列表理解(因此是c for c in coinValueList)，只是为了在上面添加if c <= cents子句。然后将其用作标准for x in iterable:表达式的可迭代项。我怀疑这就是你有些困惑的原因。
写这行的另一种方式可能是：
...
for eachCoinValue in filter(lambda x: x <= cents, coinValueList):
...
或者更明确地说，"意图揭示变量"是：
...
smallEnoughCoins = filter(lambda each: each <= cents)
for each in smallEnoughCoins:
...