322. Coin Change

Leetcode #: 322
Name: Coin Change
Difficulty: Medium
Url: https://leetcode.com/problems/coin-change/

Problem Statement

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.

Example

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

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Approach

Greedy Strategies

We can attempt to solve this problem using Greedy strategies / algorithms; however, we’re going to find out that this strategy won’t work because we won’t get the minimum combination of coins to produce the given amount.

For instance, given the coins [1, 3, 4, 5] and the amount 7, using Greedy strategies lead us to the combinations of 5 + 1 + 1 instead of 3 + 4.

DFS — Backtracking

Instead of using Greedy strategies, we can plot / map the options on a tree in which each node in the tree would have 4 branches (i.e. 4 branch recursion) for the same arbitrary example if you’re given coins [1, 3, 4, 5] and the amount 7 where each branch represents a coin from our coins list.

We can map out all the possibilities starting with the root node of the given amount 7 and once we’ve hit a 0, we know that we’ve reached a leaf node which ultimately formulates a valid path or combination of coins that adds up to the given amount.

We’ll realize that once we find all of the valid paths or combinations, we can compare them and see which one consists of the minimum path or combination to form the provided amount.

Top-Down DP: Memoization (Caching)

Furthermore, what we’ll notice from drawing out the tree further is that there are repeated subproblems throughout the tree. Therefore, we can save from doing redundant work by storing solved subproblems into a cache or Hash Map which will allow us to retrieve what that subproblem size equated to from our cache once we’ve encountered or visited it again.

Bottom-Up DP (True DP)

An alternative approach in solving this problem would be to start from the bottom of a valid path and work our way back up. In this example, it would be start from 0 because there are 0 ways to make 0 coins and then solve each subproblem 1-by-1 back up until we reach our original given subproblem for the problem.

The key here is to make sure that we initialize our starting point to be 0 as this will be crucial for our algorithm to calculate what the subproblem size of 1 is, then 2, 3, 4, and etc.

Finally, as we’re calculating and building up our subproblem from 0 incrementally. We’ll notice that to solve larger subproblems, we can resort to using the smaller subproblems that we’ve solved previously (i.e. DP[7] = 1 + DP[6] or 1 + DP[4] or 1 + DP[3] or 1 + DP[2]). We are adding 1 with each of these combinations because the 1 itself represents a coin from the given input coins array. For instance, if we’re given [1, 3, 4, 5] as the list of coins and the amount is 7, then DP[7] = 1 + DP[6] means that 1 equals to the 1 coin from our list of coins and DP[6] represents the number of ways we can formulate an amount of 6 using the same list of coins.

Code

Python | Time: O(amount * len(coins)) | Space: O(amount) | In the worst case scenario, the DP array will store a potential value for every single amount.

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub