Coin Change
Explore how to solve the Coin Change problem by applying dynamic programming concepts. Understand how to compute the minimum number of coins required to form a target amount given infinite coin denominations. This lesson guides you through problem constraints, clear problem understanding, and hands-on implementation to build your coding interview skills.
We'll cover the following...
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
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Coin Change
What’s the minimum number of coins required to make up the given total with the following set of coins?
coins = [1, 2, 3, 4].
total = 11.
-1
3
11
0
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
import java.util.*;public class CoinChange{public static int coinChange(int [] coins, int total) {// Replace this placeholder return statement with your codereturn -1;}}