动态编程最佳找零

动态编程最佳找零

在我看来，代码正在解决每个美分值直到目标美分值的问题。给定目标值

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]