Algoritmos y Estructuras de Datos

Coin change (Cambio de Monedas) - la cantidad de formas

Dado un sistema monetario que consta de n monedas, cada una con un valor positivo . Se te pide encontrar el número de maneras de obtener una suma total de x utilizando dichas monedas.
Por ejemplo, si los valores de las monedas son y necesitamos obtener 5, existen 4 maneras distintas de lograrlo: 5, 1 + 2 + 2, 1 + 1 + 1 + 2 y 1 + 1 + 1 + 1 + 1. A diferencia de combination sum, aquí el orden no importa; solo nos interesa el multiset de monedas que usamos.

Entrada

La primera línea de la entrada contiene dos enteros n (1 ≤ n ≤ 100) y x (1 ≤ x ≤ ).
La siguiente línea contiene n valores separados por espacio: (1 ≤ ≤ ).

Salida

El programa debe imprimir el número de maneras posibles de obtener x usando las monedas dadas. Dado que la respuesta puede ser muy grande, se pide imprimirla módulo .

Ejemplos

Entrada
Salida
3 5 1 2 5
4
3 9 2 3 5
3

Explicación

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, y 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

Tutorial

Observa que si almacenamos un estado d[s], donde d[s] es la cantidad de maneras distintas de obtener la suma s usando las monedas, surgiría el problema de contar varias veces el mismo conjunto de monedas. Por ejemplo, para el conjunto 1 + 2 + 2 (que debería contarse solo una vez), se contaría 3 veces debido a las diferentes permutaciones: 1 + 2 + 2, 2 + 1 + 2 y 2 + 2 + 1.
Para solucionar este inconveniente, contamos el número de formas de obtener el valor s procesando todas las monedas hasta la moneda ci (ci es el índice de la moneda en el arreglo c). Podemos decidir no usar la moneda ci en absoluto o usarla varias veces; todo esto se refleja en el estado. Entonces, nuestro estado d[s][ci] representa el número de maneras de obtener la suma s procesando todas las monedas hasta ci.
 
Existen 2 transiciones que nos llevan de ciertos estados previos a d[s][ci] (donde el índice de la moneda actual es ci y su valor es val):
  1. No usar la moneda ci → d[s][ci - 1]
  1. Usar la moneda ci de 0, 1, 2, … k veces → d[s - val][ci]
Así, el número total de maneras de obtener la suma s con las monedas hasta ci será la suma de todas las transiciones anteriores descritas.
 
c = [...]
x = ...
# Inicializa d con x+1 filas y len(c) columnas de 0
d = [[0] * len(c) for _ in range(x + 1)]
Podemos comenzar procesando la primera moneda y actualizar el estado d[s][0] para todas las sumas s posibles, utilizando la primera moneda. Luego pasamos a la segunda moneda y actualizamos todos los estados d[s][1]. Luego a la tercera, actualizamos d[s][2] y así sucesivamente hasta llegar a la última moneda.
Tras procesar todas las monedas, podemos imprimir el número de maneras de llegar a la suma x consultando el estado final: d[x][len(c) - 1]:
for ci, val in enumerate(c):      # Iteramos las monedas una por una
    d[0][ci] = 1                  # Es posible obtener la suma 0 sin utilizar monedas
    for s in range(1, x + 1):     # Iteramos sobre todas las sumas desde 1 hasta x inclusive
        if ci - 1 >= 0:           # (1) No usar ci en absoluto
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) Usar ci para 0 o más veces
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 ¿Puedes pensar en cómo usar un arreglo unidimensional para d?
Procesamos las monedas de una en una, así que podemos descartar todos los estados calculados para la moneda ci - 2 y anteriores. En cada iteración, solo nos interesa la moneda actual ci y la moneda previa ci - 1. Por ello, podemos usar un arreglo para la moneda anterior y otro para la moneda actual.
😎 ¿Puedes pensar en una forma de no usar ningún arreglo auxiliar y solo emplear un d unidimensional?
Podemos notar que la única operación que proviene del estado de la moneda anterior es sumar prev[s] a d[s]. Por ello, podemos prescindir de mantener un segundo arreglo:
# Inicializa d con x+1 elementos
d = [1] + [0] * x                 # Es posible obtener la suma 0 sin utilizar monedas

for ci, val in enumerate(c):      # Iteramos las monedas una por una
    for s in range(1, x + 1):     # Iteramos sobre todas las sumas desde 1 hasta x inclusive
        if s - val >= 0:          # (2) Usar ci para 0 o más veces
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue