[LeetCode] 0322. Cambio de moneda

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Te dan una matriz de números enteros monedas Representando monedas de diferentes denominaciones y un número entero. cantidad que representa una cantidad total de dinero.

Devolver la menor cantidad de monedas que necesitas para completar esa cantidadSi esa cantidad de dinero no se puede compensar con ninguna combinación de monedas, devuélvela. -1.

Puedes suponer que tienes un número infinito de cada tipo de moneda.

Ejemplo 1:

Aporte: monedas = [1,2,5], cantidad = 11
Producción: 3
Explicación: 11 = 5 + 5 + 1

Ejemplo 2:

Aporte: monedas = [2], cantidad = 3
Producción: -1

Ejemplo 3:

Aporte: monedas = [1], cantidad = 0
Producción: 0

Restricciones:

1 <= monedas.longitud <= 12
1 <= monedas[i] <= 2 ³¹ - 1
0 <= cantidad <= 10 ⁴

Pitón

				
					desde functools importe lru_cache al escribir import Lista clase Solución: def coinChange(self, monedas: Lista[int], cantidad: int) -> int: @lru_cache(Ninguno) def dfs(cantidad): si cantidad < 0: devuelve -1 si cantidad == 0: devuelve 0 min_cost = float('inf') para moneda en monedas: res = dfs(cantidad - moneda) si res != -1: min_cost = min(min_cost, res+1) devuelve -1 si min_cost == float('inf') else min_cost devuelve dfs(monto)

Medio

Pitón

Artículos relacionados