• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Example 3:
Input: coins = [1], amount = 0
Output: 0

Example 4:
Input: coins = [1], amount = 1
Output: 1

Example 5:
Input: coins = [1], amount = 2
Output: 2

Solution:

This problem has striking similarity with Unbounded Knapsack Concept. (1) We have unlimited supply of each items (coins) and (2) we need to meet exactly the amount specified.

For every coin denomination we compute the coin count to make up the amount (1) by INCLUDING one or more instances of that coin denomination, and (2) by NOT INCLUDING an instance. We take the minimum of these two computations. The code below would clarify the idea.

Top-Down Dynamic programming Solution with 2D Tabulation:



Java Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.


Bottom-Up Solution with Space Optimization:


We would be using the template discussed in Unbounded Knapsack Concept chapter to implement an efficient Dynamic Programming solution, as shown below:

Java Code:



public int coinChangeSpaceOptimized(int[] coins, int amount) {
    int[] dp = new  int[amount + 1];
        
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int coinIndex = 0; coinIndex < coins.length; coinIndex++) {
        if (coins[coinIndex] <= amount) {
            dp[coins[coinIndex]] = 1;
        }
    }
        
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}



Python Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.


Tip:


Often times if a problem mentions that you can include an element as many time as you want (or, infinitely), there is a chance that the problem could be solved using Unbounded Knapsack Concept.

The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave