Solution: Coin Change
Explore how to solve the coin change problem by applying dynamic programming techniques. Understand the limitations of naive and greedy methods, then learn to build an optimized solution using top-down memoization. This lesson helps you grasp how to break down problems into subproblems, improve efficiency, and implement a function that returns the minimum coins needed to make a target amount.
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] -
...