Saltar al contenido

Cambio exacto con monedas ilimitadas

Fácil#unbounded-knapsack#bottom-up-dp~15 min

La misión

Problema

Una máquina expendedora tiene una cantidad ilimitada de monedas de cada denominación listada en coins. Devuelve True si puede dar de cambio exactamente amount; si no, devuelve False.

Ejemplos

Input:  coins = [4, 7], amount = 15
Output: True
Por qué: 4 + 4 + 7 = 15
Input:  coins = [4, 6], amount = 9
Output: False
Por qué: toda combinación de 4 y 6 es par
Input:  coins = [5], amount = 0
Output: True
Por qué: caso límite: pagar cero no necesita monedas

Pistas

0 / 3

Tiempo objetivo
O(len(coins) · amount)
Espacio objetivo
O(amount)

Restricciones

  • unlimited supply of every coin

¿Lo que te frena es la idea y no el código? Coin Change lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio