Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Medium

Coin Change

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 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`. You may assume that you have an infinite number of each kind of coin.

Examples

Input:coins = [1,2,5], amount = 11
Output:3
11 = 5 + 5 + 1
Input:coins = [2], amount = 3
Output:-1
The amount of 3 cannot be made up with just coins of denomination 2.
Input:coins = [1], amount = 0
Output:0
0 coins are needed to make amount 0.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Dynamic Programming (Bottom-Up)

Approach

We can build a DP array `dp` where `dp[a]` is the minimum number of coins needed to make up amount `a`. We initialize `dp` with an arbitrarily large value (like `amount + 1`) because the maximum number of coins we could possibly use is `amount` (if we have a coin of denomination 1). We set `dp[0] = 0`. Then, for each amount from 1 to `amount`, we check all available coins. If `a - coin >= 0`, we can transition from `dp[a - coin]`. We update `dp[a] = min(dp[a], 1 + dp[a - coin])`. Finally, if `dp[amount]` is still the large initial value, it means the amount cannot be made up, so we return `-1`.

Complexity Analysis

Time Complexity
O(amount * len(coins))
Space Complexity
O(amount)

Time complexity is O(amount * len(coins)) because we iterate through all amounts and for each amount, we iterate through all coins. Space complexity is O(amount) for the DP array.

Solution.java
class Solution {    public int coinChange(int[] coins, int amount) {        int[] dp = new int[amount + 1];        // Initialize with a value larger than any possible answer        Arrays.fill(dp, amount + 1);        dp[0] = 0;                // Calculate minimum coins for each amount from 1 to amount        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (a - coin >= 0) {                    dp[a] = Math.min(dp[a], 1 + dp[a - coin]);                }            }        }                return dp[amount] != amount + 1 ? dp[amount] : -1;    }}