Given a variety of coin denominations existing in a currency system, find the total number of ways a given amount of money can be expressed using coins in that currency system. Assume infinite supply of coins of every denomination.

**Example**

Input: *coins *= [1, 2, 3], *amount *= 3

Output: 3

The three ways are -

- Using the coin having denomination 1 thrice
- Using the coin having denomination 3 once
- Using the coin having denomination 2 once and using the coin having denomination 1 once

**Notes**

Two ways are considered different if they use a different number of coins of any particular denomination.

As the answer can be quite large, return it modulo 1000000007.

Constraints:

- 1 <=
*total number of denominations*<= 100 - 1 <=
*denomination of a coin*<= 10000 - 1 <=
*amount to be expressed*<= 10000

We have provided four solutions.

First, we shall explain a brute force solution using recursion. Then we will be using both iterative and recursive dynamic programming to optimize the brute force solution. Finally we will introduce a nice trick to optimize the memory complexity of our solution with iterative dynamic programming.

The most effective way to approach a dynamic programming problem is -

- Solve the problem for trivial cases, also known as the
**base cases**. - Figure out how the problem can be broken into smaller sub-problems. You also need to figure out which set of variables is necessary and sufficient to pinpoint the current sub-problem that we are trying to solve. This set of variables is known as the
**states**of the problem. - Figure out the relationship between the solution to the smaller subproblems and the solution of the whole problem. This relationship, known as the
**recurrence relation**, can be expressed as a recursive function whose parameters are the states of the problem.

How to identify that the problem can likely be solved by the dynamic programming paradigm -

- Gain experience. If you solve various problems from different domains of algorithms, then you will start to observe a pattern in the dynamic programming problems.
- Try to break the problem into smaller subproblems and find the relationship between the solution to the smaller sub-problem and the solution to the whole problem. If you can, then most likely the problem can be solved with the dynamic programming paradigm.
- Try to convert the given problem to one of your known dynamic programming problems.

In the following solutions, we would be assuming that there are *n *different denominations.

Let the recursive function make_change(*idx*, *target*) return the number of ways to make *target *by using the coins from indices 0 to *idx,* **inclusive**. By definition, make_change(*n - 1*, *amount*) is what we need to return.

The base cases for this recursive function are:

- When we are at
*idx = -1*, we need to check if we have*target == 0*or not. - We can return 0 whenever we have a negative
*target*.

Now let us focus on how to compute make_change(*idx, target*). We can make the amount *target *in two ways.

**by using the coin at index**: If we use the coin at index*idx**idx*, our next goal would be to make*target - coins[idx])*by using the coins from indices 0 to*idx*. Here*coins[idx]*is the denomination of the coin at index*idx*. There are make_change(*idx, target - coins[idx]*) ways in total by definition. Notice that in the following call, even though we updated the parameter*target*, we did not change the parameter*idx*because we were allowed to use a coin as many times as we wanted.**by not using the coin at index**: By definition, there are make_change(*idx**idx - 1, target*) ways in total to do so.

If we combine the two cases, we get the following recurrence relation:

make_change(*idx, target*) = ( make_change(*idx-1, target*) + make_change(*idx, target - coins[idx]*) ) % 1000000007. The mod operation has been used as we need to output the result modulo 1000000007.

**Time Complexity:**

Exponential.

There are 2*n* - 1 different subsets of the given coins which we can choose to use to make *amount*. In each such selection, we can choose to use any type of coin, any number of times. So our solution will try out at least 2n - 1 different solutions in the worst case. Hence the complexity is exponential.

**Auxiliary Space Used:**

O(*n + amount*).

Here the auxiliary space is mostly used to maintain the call stack of the recursive calls. It is dominated by the highest possible depth of the call stack. As the smallest denomination for a coin can be equal to 1, so we can not use a coin more than *amount *times. Also, as we can skip at most *n - 1 *coins in total to make *amount. *So in the worst case, we may have a call stack of depth of O(*n + amount*).

**Space Complexity:**

Space used for input: O(*n*).

Auxiliary space used: O(*n + amount*).

Space used for output: O(1).

So total space complexity: O(*n + amount*).

Notice that in the above recursive solution, we may call the make_change(*idx, target*) function multiple times with the same parameters.

For instance, consider the given example: There are 3 coin denominations: 1, 2 and 3 and we have to make the *amount* 3.

*coins[ ] = *{1, 2, 3}

*amount = *3.

Considering that we started from *idx = n - *1* *and *amount = *3 state, there are two ways to reach *idx *= 0 and *target *= 1 state,

- By using the coin at
*idx*= 1 once. - By using the coin at
*idx*= 0 twice.

As the output of make_change(*idx, target*) is constant, we do not need to compute this output more than once. We can store the result after computing the answer for make_change(*idx, target*) once. This optimization technique is known as memoization. The data structure that we should use for storing the data depends on the domain of the variables *idx* and *target*. There can be *n* different values of *idx *and *target *can range from 0 to *amount*. Both of the domains of the variables form a consecutive range. So it would be better to use a two dimensional static array than a hash table.

**Time Complexity:**

O(*n * amount*).

There are (*n * amount*) different possible states which we may need to compute in the worst case. So the time complexity is equal to O(*n * amount*).

**Auxiliary Space Used:**

O(*n*amount*) space has been used for memoization.

**Space Complexity:**

Space used for input: O(*n*).

Auxiliary space used: O(*n * amount*).

Space used for output: O(1).

So total space complexity: O(*n * amount*).

Let dp[*idx*][*target*] be the number of ways we can make *target *using coins from indices less than or equal to *idx, ***inclusive**. By definition, dp[*n - 1*][*amount*] is what we need to return. dp[*idx*][0] = 1 holds for all *idx *between 0 to *n* -1 as we can always make 0 in one way ( by not using any coin at all ). This is the base case of our solution.

Now let us focus on how to compute dp[*idx* , *target*]. We can make the amount *target *in two ways.

**by using the coin at index**If we use the coin at index*idx*:*idx*, our next goal would be to make (*target - coins[idx]*) by using the coins from indices between 0 to*idx*. Here*coins*[*idx*] is the denomination of the coin at index idx. There are*dp*[*idx*][*target - coins*[*idx*]]*idx*because we were allowed to use a coin as many times as we wanted.**by not using the coin at index**By definition, there are dp[*idx*:*idx - 1*][*target*] ways in total to do so.

If we combine the two cases, we get the following recurrence relation:

dp[*idx*][*target*] = (dp[*idx - 1*][*target*] + dp[*idx*][*target-coins*[*idx*]]) % 1000000007

Be careful to fill up the dp table in the right order. While computing a cell in the table, make sure that those cells who contribute to this cell have already been computed. In this problem incrementing *idx *from 0 to *n* - 1 and incrementing the *target *from 0 to *amount* works.

**Time Complexity:**

O*(n * amount*).

There are (*n * amount*) different possible states which we may need to compute. So the time complexity is equal to O*(n * amount*).

**Auxiliary Space Used:**

O(*n*amount*) space has been used for the dp table.

**Space Complexity:**

Space used for input: O(*n*).

Auxiliary space used: O(*n * amount*).

Space used for output: O(1).

So total space complexity: O(*n * amount*).

The dp table that we computed in our previous solution had a size of (*n * amount*). Let us call it the "complete dp table". The complete dp table can be thought of as a table with *n* rows and *amount *columns. In our solution, we will fill up the table row by row. Notice that, while computing any cell of a row, we only need the information from the immediate previous row. So we do not need to store all the rows of the complete dp table. Only the data of the immediate previous row and current row which we are computing needs to be stored. Our optimized dp table has 2 rows and *amount *columns. We will be cyclically using these two rows to compute our solution. While computing the rows, the data of the *i*-th row from the complete dp table will be stored in (*i* % 2)-th row of our optimized dp table. So whenever we are computing any row of the dp table, we will have the information of the previous row. For example, suppose we are trying to compute the dp table for the test case: *coins* = [ 9, 1, 8, 10, 3 ], *value* = 12.

The complete dp table looks as follows:

Now let us construct the optimized dp table. The 0th row can be computed without the help of any other row and the 1st row can be computed with the help of the 0-th row. So after computing the first two rows, our optimized dp table will look like:

At this stage, we do not need the information from the 0-th row. So we can overwrite this memory to store information about the 2nd row of the complete dp table.

Similarly in this stage, we can replace the information of the 1st row with the new information from the 3rd row of the complete dp table.

Finally, on the last iteration, the table will look like:

But can we do better? Turns out that we can discard one of the two rows. Let us focus on the recurrence relation:

dp[*idx*][*target*] = (dp[*idx - 1*][*target*] + dp[*idx*][*target-coins*[*idx*]])

Notice that any cell contributes only its value to the next row of the same column. In other words, when moving from one row to another, we add some other value over the already existing value of that column. For this reason, we can use a one-dimensional array of size *amount *and add to the existing array data while moving from one row to the next row.

**Time Complexity:**

O(*n * amount*).

**Auxiliary Space Used:**

O(*amount*) space has been used for the dp table.

**Space Complexity:**

Space used for input: O(*n*).

Auxiliary space used: O(*amount*).

Space used for output: O(1).

So total space complexity: O(*n + amount*).

Note: Input and Output will already be taken care of.