Loading...
Loading...
Loading...
A till has coins of distinct values, as many of each as needed. Count the different ways to pay the amount, where two ways are the same if they use the same number of each coin. Print the count.
Example 1
Input
1 2 5 5
Output
4
The ways are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.
Example 2
Input
2 3
Output
0
Try the problem first. Open one hint at a time.
Put the coin loop on the outside and the amount loop on the inside.
dp[0] = 1 because paying 0 can be done in exactly one way.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor