He estado revisando algunos problemas de programación dinámica, y me ha costado mucho darme cuenta de algo de código para encontrar el menor número de monedas para hacer cambios.

Digamos que tenemos monedas por valor de 25, 10 y 1, y estamos haciendo un cambio para 30. Greedy devolvería 25 y 5 (1) mientras que la solución óptima devolvería 3 (10). Aquí está el código del libro sobre este problema:

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]

Si alguien pudiera ayudarme a envolver mi cabeza con este código (la línea 4 es donde empiezo a confundirme), sería genial. ¡Gracias!