Total number of ways to get denomination of coins.

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.

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.

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++

#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

4 Coin changes are possible for amount_value = 6.