- Prepare
- Algorithms
- Dynamic Programming
- The Coin Change Problem

# The Coin Change Problem

# The Coin Change Problem

Given an amount and the denominations of coins available, determine how many ways change can be made for amount. There is a limitless supply of each coin type.

**Example**

There are ways to make change for : , , and .

**Function Description**

Complete the *getWays* function in the editor below.

getWays has the following parameter(s):

*int n:*the amount to make change for*int c[m]:*the available coin denominations

**Returns**

*int:*the number of ways to make change

**Input Format**

The first line contains two space-separated integers and , where:

is the amount to change

is the number of coin types

The second line contains space-separated integers that describe the values of each coin type.

**Constraints**

- Each is guaranteed to be distinct.

**Hints**

*Solve overlapping subproblems using Dynamic Programming (DP):*

You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
* Consider the degenerate cases:

- How many ways can you make change for cents?
- How many ways can you make change for cents if you have no coins?
* If you're having trouble defining your solutions store, then think about it in terms of the base case .
- The answer may be larger than a -bit integer.

**Sample Input 0**

```
4 3
1 2 3
```

**Sample Output 0**

```
4
```

**Explanation 0**

There are four ways to make change for using coins with values given by :

**Sample Input 1**

```
10 4
2 5 3 6
```

**Sample Output 1**

```
5
```

**Explanation 1**

There are five ways to make change for units using coins with values given by :