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