- Dynamic Programming
- 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.
There are ways to make change for : , , and .
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
- int: the number of ways to make change
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.
- Each is guaranteed to be distinct.
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
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
There are five ways to make change for units using coins with values given by :