Coin change problem
Lesson 8 of 15 in Coddy's Dynamic Programming 101 course.
The coin change problem is a classic problem in dynamic programming. Given a set of coins with different denominations and a total amount of money, the task is to find the minimum number of coins needed to make up the given amount.
For example, suppose we have coins with denominations [1, 5, 10] and we want to make up the amount 15. The minimum number of coins needed would be 2 (a 10 coin and a 5 coin).
To solve this problem using dynamic programming, we can create a table with rows representing the denominations of coins and columns representing the amounts from 0 to the given total amount. We then fill in the table in a bottom-up manner by computing the minimum number of coins needed to make up each amount using the coins of each denomination.
Challenge
MediumWrite a program that takes in two inputs: a list of coin denominations and a target amount, and returns the minimum number of coins needed to make up the target amount.
For example, for the denominations [1, 5, 10] and the target amount 15, the output should be 2.
Try it yourself
def min_coins(coins, target):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance