This is a variant of the previous problem. Like previous coin change problem, we shall solve with help of** Dynamic Programming.**

## Problem Statement:

You are given total amount and certain coin denomination. You need to get the total number of ways you make the change.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Example: Amount Value = 6 Coins = 1, 3, 6 Number of ways = 1 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1+ 1 + 3 3 + 3 6 As you can see above you have 4 different ways. |

So similar to previous example, we shall solve it using DP.

Below will be our DP table.

So if you have only 1 coin, the total number of ways you can arrange will be only 1. Hence we write 1 in all the cells.

Now you have [1, 3] coin, the total number of ways till rupee 3 will be 1 only.

Now when you are at 3 rupees, the total number of ways will be 2. Because you can have 3 one rupees coin or one 3 rupees coins.

Similarly, you can calculate for 4 rupees i.e 2 different ways.

1 + 1 + 1 + 1 = 4

1 + 3 = 4

Similarly, for 5 rupees it will be 2.

Similarly, for 6 rupees it will be 3. Because all 2’s or two 3’s or all 1’’s.

## But how can we convert into a formula?

If you observe at 3 rupees, the value 2 can be got by adding the value from top and value for 3 steps before.

1 |
add(value_ar_top + value_at_3_steps_back) |

Similarly, for rupees 4

Similarly, for rupees 5

Similarly, for rupees 6

Similarly, we can calculate when we have 3 choices. Till 5 rupees, we can copy the value from above cell.

When you have 6 rupees, apply the above formula.

As you are choosing 6 rupees’ coin, you need to go 6 steps back.

Hence the solution.

## Implementation of Total number of ways to get denomination of coins in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <vector> using namespace std; int get_total_number_of_denominations_available (vector<int> &coins, int amount_value) { int m = coins.size(); int *table = (int*) calloc (amount_value+1, sizeof(int)); table[0] = 1; for (int i = 0; i < m; i++) { for (int j = coins[i]; j <= amount_value; j++) { table[j] += table[j-coins[i]]; } } return table[amount_value]; } int main (void) { vector <int> coins; coins.push_back (1); coins.push_back (3); coins.push_back (6); int amount_value = 6; int num_of_ways = get_total_number_of_denominations_available (coins, amount_value); cout << num_of_ways << " Coin changes are possible for amount_value = " << amount_value << "." << endl; return 0; } |

## Output:

1 |
4 Coin changes are possible for amount_value = 6. |