Algoritmos y Estructuras de Datos (VJ1215)

Por ejemplo, si monedas = {5, 21, 1, 25} y deuda = 63, hay cuatro opciones para devolver la primera moneda, y hemos de elegir la mejor de las cuatro:

mínimaCantidadMonedas(63) = min(1 + mínimaCantidadMonedas(63 - 5),
                                1 + mínimaCantidadMonedas(63 - 21),
                                1 + mínimaCantidadMonedas(63 - 1),
                                1 + mínimaCantidadMonedas(63 - 25))
      

Con n monedas habrá n opciones a elegir, salvo si hay monedas de valor superior a la deuda, en cuyo caso se descartan:

mínimaCantidadMonedas(7) = min(1 + mínimaCantidadMonedas(7 - 5),
                               1 + mínimaCantidadMonedas(7 - 1))