在我看来，代码正在解决每个美分值直到目标美分值的问题。给定目标值
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]
