Coin Change 2
Advanced
You're a young explorer on a quest to find a hidden treasure. According to ancient maps, to unlock the treasure chest, you need to find the exact amount of gold coins. However, your treasure bag contains various denominated coins! But fret not, your task is to figure out the different ways you can combine these coins to make up a specific amount. Let's use Python to solve this!
Write a function coin_change_ways that calculates the number of different combinations that can make up a given amount using a set of coin denominations. You have an unlimited number of each type of coin.
Examples:
# Example 1 coin_change_ways(5, [1, 2, 5]) # Output: 4 # Explanation: There are four ways to make change for 5: # (1=5), (2+2+1), (1+1+1+1+1), (5) # Example 2 coin_change_ways(3, [2]) # Output: 0 # Explanation: No combination can make 3 with only denomination 2. # Example 3 coin_change_ways(10, [10]) # Output: 1 # Explanation: There is only one way to make 10 which is (10).
Hints:
- Think about how you can use dynamic programming to store the number of ways to make each amount incrementally.
- Start with an array
wayswhereways[i]represents the number of ways to create the amounti. - Initialize
ways[0]to 1 because there is one way to make the amount 0: using no coins at all.
Inputs
Arg 1:
5Arg 2:
[1,2,5]Expected Output
4Actual Output