Solution: Coin Change
Explore how to solve the coin change problem using dynamic programming. This lesson guides you to understand why greedy algorithms fail here and how breaking the problem into subproblems leads to an optimal solution. You'll implement a top-down memoized approach that calculates the minimum number of coins needed, improving time efficiency significantly compared to naive recursion.
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] ...