Coin Change

Q: ¿Cuál es la complejidad temporal de Coin Change?

La solución de programación dinámica tarda O(amount × coins) y ocupa O(amount) de espacio: una entrada de la tabla por cada cantidad, y se comprueba cada moneda para cada entrada. La recursión simple sin memoización tiene un tiempo exponencial respecto a la cantidad.

Q: ¿Es mejor el enfoque descendente o el ascendente para el problema del cambio de monedas?

Ambos realizan el mismo trabajo O(amount × coins) . La recursión de arriba hacia abajo puede anidarse hasta alcanzar la cantidad, lo que desborda la pila de llamadas con 10^4 en varios lenguajes. El enfoque de abajo hacia arriba llena la tabla con un bucle, por lo que no tiene límite de profundidad y es la opción más segura en una entrevista.

MedioProgramación dinámica

+10

Recibes una lista coins de valores de monedas diferentes y una cantidad objetivo amount. Puedes usar cada valor de moneda tantas veces como quieras. Devuelve el menor número de monedas cuyos valores sumen exactamente amount, o -1 si ninguna combinación de monedas permite alcanzarla. Una cantidad de 0 requiere 0 monedas.

Función

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: los distintos valores de las monedas, cada uno utilizable cualquier número de veces
amountinteger: el total exacto que hay que pagar
Devuelveinteger: la menor cantidad de monedas necesaria, o -1 cuando no se pueda obtener el importe

Restricciones

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Todos los valores de las monedas son diferentes.

Ejemplos

Entrada: coins = [2, 5, 10]amount = 27
Salida: 4
Explicación: 10 + 10 + 5 + 2 suman 27 con cuatro monedas. Con tres monedas no se puede: 27 es impar, así que necesitan exactamente una de 5, y las otras dos suman como máximo 20, menos de 22.

Para ir más allá

¿Puedes contar cuántas combinaciones diferentes de monedas suman amount, en lugar de encontrar la menor cantidad de monedas?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Elegir la moneda más grande que quepa falla: con monedas de 1, 3 y 4, paga 6 como 4 + 1 + 1, mientras que 3 + 3 necesita dos monedas. La cantidad mínima de monedas para un importe depende únicamente de la cantidad mínima de monedas para importes menores, así que resuelves cada importe desde 0 hasta amount una vez.

Prueba todas las combinaciones con recursión

Correcto, pero no termina con las pruebas más grandes

Intuición

Si la última moneda que pagas vale c, las monedas anteriores suman remaining - c con el menor costo posible. Así que fewest(remaining) es uno más que el mejor fewest(remaining - c) entre todas las monedas que caben. Esto prueba todas las secuencias de monedas que no se pasan, así que no puede pasar por alto la mejor.

Resuelve las mismas cantidades una y otra vez. Con monedas de 2, 5 y 10, la cantidad 27 llega a 15 después de pagar 10 + 2, 2 + 10, 5 + 5 + 2 y más órdenes, y calcula 15 desde cero cada vez. El número de llamadas crece exponencialmente con la cantidad.

Algoritmo

Escribe una función auxiliar fewest(remaining) que devuelva la menor cantidad de monedas para remaining, o -1 si ninguna sirve.
Si remaining es 0, devuelve 0.
Para cada moneda que no sea mayor que remaining, llama a la función auxiliar con lo que queda después de pagar esa moneda.
Conserva el resultado más pequeño que no sea -1, más uno por la moneda que pagaste.
Devuelve esa cantidad, o -1 si ninguna moneda dio resultado. La respuesta es fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Recursión con memoización

Correcto, pero no termina con las pruebas más grandes

Intuición

La recursión solo pregunta por cantidades de 0 a amount. Guarda cada respuesta en un arreglo la primera vez que la calcules y devuelve el valor guardado cuando esa cantidad vuelva a aparecer. Cada cantidad se resuelve una vez con un bucle sobre las monedas: O(amount × coins) de trabajo.

Las llamadas siguen anidándose un nivel por cada moneda pagada. Con una moneda de valor 1, se alcanzan hasta 10^4 niveles, más de los que permite la pila de llamadas predeterminada en muchos lenguajes.

Algoritmo

Crea un array memo con espacio para todas las cantidades de 0 a amount, que contenga un marcador que signifique que aún no se ha calculado.
En fewest(remaining), devuelve 0 para 0 y devuelve memo[remaining] si ya contiene una respuesta.
De lo contrario, prueba cada moneda que quepa, como en la recursión simple, y conserva el resultado más pequeño más uno.
Guarda el resultado, incluido -1, en memo[remaining] antes de devolverlo.
Devuelve fewest(amount).

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Programación dinámica ascendente sobre cantidades

Intuición

Completa una tabla fewest desde 0 hacia arriba. Cuando llegues a un total t, todos los totales menores ya estarán resueltos, así que fewest[t] es uno más que el menor valor de fewest[t-c] entre las monedas c que caben.

Los totales a los que no se llega con ninguna combinación de monedas conservan el marcador amount + 1. Cada moneda vale al menos 1, así que una respuesta real nunca usa más de amount monedas y el marcador pierde en todas las comparaciones. Un bucle reemplaza la recursión, así que la profundidad de la pila de llamadas nunca importa.

Algoritmo

Crea fewest con amount + 1 entradas, todas establecidas en el marcador amount + 1, y establece fewest[0] en 0.
Para cada total t de 1 a amount, revisa cada moneda c que cumpla c ≤ t.
Si fewest[t-c] + 1 es menor que fewest[t], guárdalo en fewest[t].
Después del bucle, devuelve -1 si fewest[amount] aún contiene el marcador; en caso contrario, devuelve fewest[amount].

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Errores comunes y casos límite

Tomar primero la moneda de mayor valor. Con monedas de 3 y 5 y una cantidad de 9, se usan 5 y 3, se queda atascado en 1 y devuelve -1, mientras que 3 + 3 + 3 funciona.
Usar el entero más grande como marcador. Al sumarle 1, se desborda y se convierte en un número negativo, que luego gana todas las comparaciones. Usa amount + 1.
Sumar 1 a un callejón sin salida. Una rama que devuelve -1, más la moneda que pagaste, da 0 y gana todas las comparaciones. Omite los resultados -1.
Recurrir amount niveles de profundidad. Con una moneda de valor 1 y una cantidad de 10^4, Python se detiene al alcanzar su límite predeterminado de 1000 niveles, y JavaScript, Dart, Ruby y R también se quedan sin espacio en la pila.
Leer fewest[t-c] para una moneda mayor que t, antes del inicio de la tabla.

Preguntas frecuentes3

¿Por qué falla el enfoque voraz para el problema del cambio de monedas?

Tomar la moneda más grande que quepa solo es seguro para algunos sistemas de monedas, como la mayoría de las monedas reales. Con monedas de 1, 3 y 4, paga 6 con tres monedas en lugar de dos, y con monedas de 3 y 5 no puede pagar 9 en absoluto. La programación dinámica compara todas las opciones, así que ningún sistema de monedas la engaña.

¿Cuál es la complejidad temporal de Coin Change?

La solución de programación dinámica tarda O(amount × coins) y ocupa O(amount) de espacio: una entrada de la tabla por cada cantidad, y se comprueba cada moneda para cada entrada. La recursión simple sin memoización tiene un tiempo exponencial respecto a la cantidad.

¿Es mejor el enfoque descendente o el ascendente para el problema del cambio de monedas?

Ambos realizan el mismo trabajo O(amount × coins). La recursión de arriba hacia abajo puede anidarse hasta alcanzar la cantidad, lo que desborda la pila de llamadas con 10^4 en varios lenguajes. El enfoque de abajo hacia arriba llena la tabla con un bucle, por lo que no tiene límite de profundidad y es la opción más segura en una entrevista.

def coinChange(coins, amount):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

coins = [2, 5, 10]
amount = 27

Salida Esperada

Coin Change

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba todas las combinaciones con recursión

Recursión con memoización

Programación dinámica ascendente sobre cantidades

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares