Solution: Coin Change
Explore how to solve the coin change problem by minimizing the number of coins needed to reach a target amount. Learn to use dynamic programming with top-down memoization to improve efficiency over naive recursion. This lesson guides you through problem breakdown, base case reasoning, and implementing an optimized approach to handle various coin denominations.
Statement
Given an integer total that represents the target amount of money and a list of integers coins that represents different coin denominations, find the minimum number of coins required to make up the total amount. If it’s impossible to achieve the target amount using the given coins, return -1. If the target amount is 0, return 0.
Note: You can assume that we have an infinite number of each kind of coin.
Constraints:
-
coins.length -
coins[i] -
total
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach is to generates all possible combinations of given denominations such that in each combination, the sum of coins is equal to total. From these combinations, choose the one with the minimum number of coins and return the minimum number required. If the sum of any combinations is not equal to total then print -1.
In the worst case, the time complexity increases exponentially with the total amount, which results in an algorithm edging toward