Given a certain amount of money that we have, we want to change the money into coins. What is the minimum number of coins required to make the change?
Input: int[] coins = {10, 5, 2, 1}; int amount = 12; Output: 2 Explanation: Minimum there are required 2 coins: 10 and 2. |
Solution:
1. static int minimumAmountOfCoins(int[] coins, int amount) { 2. int[] minimumAmountOfCoins = new int[amount + 1]; 3. 4. for (int i = 1; i <= amount; i++) { 5. minimumAmountOfCoins[i] = Integer.MAX_VALUE; 6. } 7. 8. for (int i = 1; i <= amount; i++) { 9. for (int coin : coins) 10. if (coin <= i) { 11. int minimumAmountOfCoin = minimumAmountOfCoins[i - coin]; 12. if (minimumAmountOfCoin != Integer.MAX_VALUE && minimumAmountOfCoin + 1 < minimumAmountOfCoins[i]) { 13. minimumAmountOfCoins[i] = minimumAmountOfCoin + 1; 14. } 15. } 16. } 17. 18. if (minimumAmountOfCoins[amount] == Integer.MAX_VALUE) { 19. return -1; 20. } 21. 22. return minimumAmountOfCoins[amount]; 23. } 24.