¿Me pueden ayudar a entender el problema del cambio de moneda?

Bien, supongamos que tiene las siguientes monedas 1, 2, 5.

Lo que tiene que hacer es crear una matriz donde el índice será la cantidad de dinero que desea cambiar, y el valor en ese índice será la cantidad mínima de monedas que necesita para eso. Aquí hay un ejemplo con las monedas de arriba.

[1, 1, 2, 2, 1]

En el índice 1 (comencé a contar desde 1) tiene un 1. Eso significa que necesita 1 moneda para cambiar 1 $ (o la moneda que desee). En el índice dos dice 1 otra vez. ¿Por qué? Porque para cambiar 2 $ necesitas una moneda, una moneda de 2 $. En el índice 3 dice 2 porque el mínimo para cambiar 3 $ es usar 2 monedas: 1 y 2 $.

Ahora supongamos que queremos saber cuál es la cantidad mínima de monedas que necesitamos para cambiar 6 $.

Tenemos todos los valores hasta 6–1, que es 5.

Como tienes 3 monedas, tienes tres opciones:

array [6] = array [5] + 1 (el valor en array [5] más una moneda de un dólar)

O

array [6] = array [4] + 1 (el valor en array [4] más una moneda de dos dólares)

O

array [6] = array [1] + 1 (el valor en array [1] más una moneda de cinco dólares)

¿Cómo obtuvimos estos números? Usted toma la cantidad de dinero que desea cambiar (en nuestro caso, 6 $) y le resta todas las monedas posibles. Terminarás con 5, 4 y 1.

Como ya sabe la cantidad de monedas que necesita para cambiar 5, 4 o 1 $, solo tiene que agregar una a ese número (agregue una moneda, ya sea 1 $, 2 $ o 5 $).

Volvamos al ejemplo. Dice:

matriz [6] = matriz [5] + 1

Ese es igual a 1 (el valor de la matriz en el índice 5; cuántas monedas necesita cambiar 5 $) + 1, que es 2

Entonces dice

matriz [6] = matriz [4] + 1

array [4] es 2 más una moneda de dos dólares es 3

Y la ultima suma

matriz [6] = matriz [1] + 1

array [1] es 1 más 1 = 2

El mínimo de estos 3 es 2. Por lo tanto, necesita 2 monedas para cambiar 6 dólares. Lo cual es correcto porque necesita una moneda de 1 $ y 5 $.

Espero haberte ayudado a entender esto.