Coin Change — Java Coding Problem
Difficulty: medium | Category: dynamic-programming
Problem Description
You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return the fewest number of coins needed to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`. Hint: Bottom-up DP — `dp[i] = min(dp[i], dp[i - coin] + 1)` for each coin.
Examples
Example 1
Input: coins = [1, 5, 10], amount = 11
Output: 2
Explanation: 10 + 1 = 11 using 2 coins.
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: Cannot make 3 with only 2-cent coins.
Example 3
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11 using 3 coins.