Expert · Dynamic programming · 215 of 264
Ways to make change
In how many ways can an amount be made from the coins (each value used any number of times)? Different orders of the same coins count once.
Input: the coin values on one line, then the amount (up to 10000). Output: the number of ways.
Examples
Input
1 2 5 5
Output
4
Input
2 3
Output
0
Input
1 5 10 25 50 100
Output
292
One more test checks other inputs when you press Check.
Stuck? The idea behind dynamic programming
Break the problem into smaller ones that repeat, and keep each answer in a table so it is worked out only once.
Decide what one cell of the table means ("the best total using the first i items"), how it follows from earlier cells, and where it starts.
n = 10
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
print(ways[n]) # climbing 10 stairs, 1 or 2 at a timeWatch for: Fill the table in an order where every cell it needs is already filled.