5.3.1. Problema del cambio de monedas.
Definición de las tablas utilizadas:
Necesitamos almacenar los resultados de todos los subproblemas.
El problema original será: Cambio (n, P).
Por lo tanto, necesitamos una tabla de nxP, de enteros, que llamaremos D, siendo D[i, j]= Cambio(i, j).
Ejemplo. n= 3, P= 8, c= (1, 4, 6)
Forma de rellenar las tablas:
De arriba hacia abajo y de izquierda a derecha, aplicar la ecuación de recurrencia:
D[i, j] = min (D[i - 1, j] , D[i, j - ci] + 1)