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.
Further Reading: