Solution: Coin Change
Explore the coin change problem where you determine the minimum number of coins needed to make a target amount using a dynamic programming approach. Understand why greedy methods fail, learn to break down the problem into subproblems, and implement an optimized solution using memoization to improve time efficiency.
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] ...