Ways to make change
Statement
Goal
Given a non-negative amount N and a set of S coins of positive values Vi, return the number of ways to reach the required amount using the coins.NB : You have an unlimited number of each coin at your disposal.
For example, given N = 10, S = 2 and the set of values V1 = {1, 5} , you should return 3. Indeed, there are 3 ways to sum coins of values {1, 5} up to 10 : 1*10, 5*2 and 1*5 + 5*1.
Input
Line 1 : A non-negative integer N for the target amount.
Line 2 : A positive integer S for the number of possible values coins.
Line 3 : S space-separated non-negative integer Vi for the value of the i-th coin.
Line 2 : A positive integer S for the number of possible values coins.
Line 3 : S space-separated non-negative integer Vi for the value of the i-th coin.
Output
An integer representing the number of ways to sum the coins up to N (0 if there is no way to reach the target amount).
Constraints
0 <= N <= 2000
0 < S <= 10
0 < Vi <= 500
0 < S <= 10
0 < Vi <= 500
Example
Input
10 2 1 5
Output
3
Tags
Dynamic programming, Loops
Difficulty
Medium
Test cases
Small change Test
Input
10
2
1 5
Output
3
Validator 1 Validator
Input
15
3
1 2 5
Output
18
Bigger change Test
Input
100
5
1 5 10 20 50
Output
343
Validator 2 Validator
Input
120
5
1 5 10 20 50
Output
585
That won't be easy ! Test
Input
9
3
5 6 10
Output
0
Validator 3 Validator
Input
17
4
5 8 10 11
Output
0
Bank notes only please Test
Input
300
7
5 10 20 50 100 200 500
Output
1022
Validator 4 Validator
Input
425
7
5 10 20 50 100 200 500
Output
3248
How am I supposed to do ?! Test
Input
413
2
5 10
Output
0
Validator 5 Validator
Input
172
1
10
Output
0
Pushing a bit... Test
Input
1000
5
1 2 3 4 5
Output
357746987
Validator 6 Validator
Input
2000
6
5 6 8 10 25 40
Output
124781564
Solution language
Solution
Stub generator input