Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. ReturnQuestion and return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Constraints:
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 2^31 - 1
Examples:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Solutions
Dynamic Programming
We use dynamic programming to solve this problem. We create a dp array of size amount + 1, where dp[i] represents the minimum number of coins needed to make up the amount i. We initialize all values in the dp array to Infinity, except for dp[0] which is 0. Then we iterate over each coin and update the dp array accordingly. Finally, we return the value of dp[amount], or -1 if it is still Infinity.
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin;
i <= amount;
i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}Follow-up:
What if the amount is very large and we need to use a more efficient algorithm?
