<p>在我看来,代码正在解决每一分钱到目标分钱的问题。给定目标值<code>v</code>和一组硬币<code>C</code>,您知道最佳硬币选择<code>S</code>必须是<code>union(S', c)</code>形式,其中<code>c</code>是来自<code>C</code>的一些硬币,而<code>S'</code>是<code>v - value(c)</code>的最佳解决方案(请原谅我的注释)。所以问题是<a href="http://en.wikipedia.org/wiki/Optimal_substructure" rel="nofollow">optimal substructure</a>。动态规划方法是解决每一个可能的子问题。它需要<code>cents * size(C)</code>步骤,而不是那些如果你试图强行直接解决的话会爆炸得更快的东西。</p>
<pre><code>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]
</code></pre>