Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Contar combinaciones de monedas

Cuenta las formas de obtener una cantidad usando monedas de denominaciones especificadas, con uso ilimitado de cada una.

Lo que aprenderás

  • Contar combinaciones, no órdenes
  • Recorrer las monedas en el bucle externo
  • Construir un array DP 1D de formas

Problema

Ver original (inglés)

Usa cualquier cantidad de cada denominación suministrada para obtener exactamente la cantidad indicada. Cuenta combinaciones, no ordenamientos: dos arreglos que usan la misma cantidad de cada moneda se consideran la misma forma. Las denominaciones son distintas y positivas.

Implementa coin_sums(amount, coins).

Entrada

amount: La cantidad total a obtener.

coins: Las denominaciones distintas disponibles.

Salida

Devuelve el número de combinaciones sin importar el orden.

Restricciones

0 ≤ amount ≤ 200. Hay entre 0 y 10 denominaciones distintas, cada una entre 1 y 200. Todos los conteos caben en un entero con signo de 64 bits. Para amount 0 hay una forma: no elegir ninguna moneda.

Ejemplos

Ejemplo 1
Entrada:
amount = 4
coins = [1, 2]

Salida esperada:
expected = 3
Entrada:
long long amount = 4;
std::vector<long long> coins = {1, 2};

Salida esperada:
long long expected = 3;
Entrada:
long amount = 4;
long[] coins = new long[] {1, 2};

Salida esperada:
long expected = 3;

Explicación

Las combinaciones son: cuatro monedas de 1, dos monedas de 1 con una de 2, y dos monedas de 2.

Ejemplo 2
Entrada:
amount = 3
coins = [2]

Salida esperada:
expected = 0
Entrada:
long long amount = 3;
std::vector<long long> coins = {2};

Salida esperada:
long long expected = 0;
Entrada:
long amount = 3;
long[] coins = new long[] {2};

Salida esperada:
long expected = 0;

Explicación

Cualquier suma usando solo monedas de valor 2 es par, así que 3 es imposible.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

El orden de las monedas no importa, así que las combinaciones deben contarse por denominación, no por permutación.

Pista 2

Construye el número de formas para cada cantidad de manera incremental, dejando que cada moneda contribuya a todos los totales alcanzables.

Pista 3

Ten cuidado con la cantidad cero, que siempre tiene una forma válida: no elegir monedas.

Complejidad esperada

tiempo O(amount × number_of_coins), espacio extra O(amount)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 811 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.