Estoy tratando de resolver el problema 322 de Leetcode . Aquí está la descripción citada del sitio.

Se le da una matriz de números enteros de monedas que representan monedas de diferentes denominaciones y una cantidad de número entero que representa una cantidad total de dinero.

Devuelve la menor cantidad de monedas que necesites para completar esa cantidad. Si esa cantidad de dinero no se puede compensar con ninguna combinación de las monedas, devuelve -1.

Puede suponer que tiene un número infinito de cada tipo de moneda.

He escrito 2 soluciones recursivas, 1 en Python y 1 en Javascript. Por alguna razón, el de Javascript no produce los valores correctos para la misma entrada, mientras que el de Python siempre lo hace.

Me gustaría preguntar si alguien sabe cuál podría ser el motivo de la diferencia en la salida. Probé con los siguientes casos de prueba:

 coins = [1,2,5], amount = 11 => Expected: 3 coins = [1,2], amount = 2 => Expected: 1

Aquí está el código que he escrito en los respectivos idiomas.

JavaScript

 var coinChange = function(coins, amount) { coins = coins.sort((a,b) => b -a ) ans = helper(coins, amount, 0) if (ans >= Number.MAX_VALUE) { return -1 } return ans; }; function helper(coins, amount, pos) { if (pos >= coins.length || amount < 0) { return Number.MAX_VALUE; } else if (amount === 0) { return 0; } left = helper(coins, amount - coins[pos], pos) + 1 right = helper(coins, amount, pos + 1) return Math.min(left, right) }

Usando los 2 casos de prueba anteriores, ambos casos de prueba son incorrectos.

 coins = [1,2,5], amount = 11 => Expected: 3, gets 2 coins = [1,2], amount = 2 => Expected: 1, gets 2

Pitón

 def coinChange(coins, amount): coins = sorted(coins, reverse = True) ans = helper(coins, amount, 0) if (ans >= float("inf")): return -1 return ans def helper(coins, amount, pos): if (pos >= len(coins) or amount < 0): return float("inf") elif (amount == 0): return 0 left = helper(coins, amount - coins[pos], pos) + 1 right = helper(coins, amount, pos + 1) return min(left, right)

Usando los 2 casos de prueba anteriores, obtiene ambas pruebas correctas.

 coins = [1,2,5], amount = 11 => Expected: 3, gets 3 coins = [1,2], amount = 2 => Expected: 1, gets 1