Dairy Queen

Interview

Time limit1sMemory limit128 MB

Summary

Count the number of ways to make N cents using unlimited coins of the given C denominations, ignoring order.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Implementation
Solved: No attempts yet

Problem

Bessie has taken a part-time job making change for customers at the local Dairy Queen restaurant. Because she has hooves instead of fingers, she uses a special cash register.

While counting out 83 cents in change one day, she wondered just how many different ways there are to do it. She could use three quarters and eight pennies, or seven dimes and three pennies, or 83 pennies — there seem to be an enormous number of possibilities.

Given a target amount of $N$ ( $1 \le N \le 300$ ) cents and a set of $C$ ( $1 \le C \le 8$ ) coin types with values $C_i$ ( $1 \le C_i \le 200$ ), count how many different ways you can make exactly $N$ cents. An unlimited number of coins of each type is available. Two ways are different when they use a different number of at least one coin type; the order in which coins are chosen does not matter.

For example, in U.S. currency 8 cents can be made with one 5-cent coin plus three 1-cent coins, and also with eight 1-cent coins. Since three pennies plus one nickel is the same as one nickel plus three pennies, 8 cents can be made in exactly two different ways. Note that some coin systems are poor at making change and yield an answer of 0.

Input

Line 1: two space-separated integers $N$ and $C$ .
Lines 2 to $C+1$ : line $i+1$ contains a single integer $C_i$ .

The coin values are listed in descending order from largest to smallest, and all values are distinct.

Output

A single line containing one integer: the number of ways to make $N$ cents of change using the given coins. The answer is guaranteed to fit in a signed 32-bit integer.

Hint

Consider recursion or dynamic programming as a solution technique.

As an illustration, here are 15 of the 159 ways to make 83 cents using coins of value 50, 25, 10, 5, and 1:

0 x 50  0 x 25  0 x 10  0 x 5  83 x 1
0 x 50  0 x 25  0 x 10  1 x 5  78 x 1
0 x 50  0 x 25  0 x 10  2 x 5  73 x 1
0 x 50  0 x 25  0 x 10  3 x 5  68 x 1
0 x 50  0 x 25  0 x 10  4 x 5  63 x 1
0 x 50  0 x 25  0 x 10  5 x 5  58 x 1
0 x 50  0 x 25  0 x 10  6 x 5  53 x 1
0 x 50  0 x 25  0 x 10  7 x 5  48 x 1
0 x 50  0 x 25  0 x 10  8 x 5  43 x 1
0 x 50  0 x 25  0 x 10  9 x 5  38 x 1
0 x 50  0 x 25  0 x 10  10 x 5  33 x 1
0 x 50  0 x 25  0 x 10  11 x 5  28 x 1
0 x 50  0 x 25  0 x 10  12 x 5  23 x 1
0 x 50  0 x 25  0 x 10  13 x 5  18 x 1
0 x 50  0 x 25  0 x 10  14 x 5  13 x 1

Examples2

Example 1
Input
```
83 5
50
25
10
5
1
```
Expected output
```
159
```
Example 2
Input
```
8 2
5
1
```
Expected output
```
2
```