- Practice
- Tutorials
- Cracking the Coding Interview
- DP: Coin Change

# DP: Coin Change

# DP: Coin Change

Check out the resources on the page's right side to learn more about dynamic programming. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.

Given a number of dollars and an array of denominations of coins, determine how many ways you can make change. For example, making change for dollars from coin denominations , there are ways to make change:

```
1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 1 1 1 1 1 1 1 5
1 1 1 1 1 1 1 1 1 1 2 2 5 5
1 1 1 1 1 1 1 1 2 2 1 1 10
1 1 1 1 1 1 2 2 2 2 10
1 1 1 1 2 2 2 2 2 2 2 1 5
1 1 2 2 2 2 2 2 2 1 1 1 5
2 2 2 2 2 2 2 1 1 1 1 1 5
```

**Hints:**

- You can solve this problem recursively, but you must optimize your solution to eliminate overlapping subproblems using Dynamic Programming if you wish to pass all test cases. More specifically, think of ways to store the checked solutions and use the stored values to avoid repeatedly calculating the same values.
- Think about the degenerate cases:
- How many ways can you make change for dollars?
- How many ways can you make change for less than dollars if you have no coins?

- If you are having trouble defining the storage for your precomputed values, then think about it in terms of the base case .

**Function Description**

Complete the function *makeChange* in the editor below. It should return the integer representing the number of ways change can be made.

makeChange has the following parameter(s):

*n*: an integer, the amount to change*coins*: an array of integers representing coin denominations

**Input Format**

The first line contains two space-separated integers, and , the amount to make change for and the number of denominations of coin.

The second line contains space-separated integers describing the denominations of each .

**Constraints**

- The list of coins contains distinct integers where each integer denotes the dollar value of a coin available in an infinite quantity.

**Output Format**

Print a single integer denoting the number of ways we can make change for dollars using an infinite supply of our types of coins.

**Sample Input 0**

```
4 3
1 2 3
```

**Sample Output 0**

```
4
```

**Explanation 0**

For and there are four solutions:

Thus, we print on a new line.

**Sample Input 1**

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

**Sample Output 1**

```
5
```

**Explanation 1**

For and there are five solutions:

Thus, we print on a new line.