# Coins Change

Python

Python : Coins Change algorithm using Dynamic Programming in Python3

C++ : Coins Change algorithm using Dynamic Programming implemented in C++11

``````#include<iostream>
#include<vector>

using namespace std;

// DP solution for making coin change
int DPGetChange (vector<int>& coinset, int biggercoin) {

int num_coins = coinset.size();
int dptable[num_coins+1][biggercoin+1];

// Coins of values greater than 0 cannot be obtained with coins of value 0
for (int c=1; c<=biggercoin; c++) {
dptable[c] = 0;
}

// Coin of value 0 can be obtained with any given coins in 1 way
for (int r=0; r<=num_coins; r++) {
dptable[r] = 1;
}

for (int r=1; r<=num_coins; r++) {
for (int c=1; c<=biggercoin; c++) {
if (c >= coinset[r-1]) {
// Exclude last coin in the coinset + Include last coin in the coinset
dptable[r][c] = dptable[r-1][c] + dptable[r][c-coinset[r-1]];
} else {
dptable[r][c] = dptable[r-1][c]; // Exclude last
}
}
}

return dptable[num_coins][biggercoin];
}

// Recursive solution for making coin change
int GetChange (vector<int>& coinset, int numcoins, int biggercoin) {

// Coin of value 0 can be obtained with any given values in 1 way
if (biggercoin == 0)
return 1;

// With no available coins for change, we cannot obtain any value
if (numcoins == 0)
return 0;

if (biggercoin >= coinset[numcoins-1])
return GetChange (coinset, numcoins-1, biggercoin) + // Get change excluding the last coin in the coin set
GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1]); // Get change including the last coin in the coin set
else
return GetChange (coinset, numcoins-1, biggercoin); // Get change excluding the last coin
}

int main(){

int coin1 = 4;
vector<int> coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */

int coin2 = 6;
vector<int> coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */

int coin3 = 10;
vector<int> coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */

cout << "Number of ways of making coin change using dynamic programming" << endl;
cout << DPGetChange (coinset_1, coin1) << endl;
cout << DPGetChange (coinset_2, coin2) << endl;
cout << DPGetChange (coinset_3, coin3) << endl;

cout << "Number of ways of making coin change using recursion" << endl;
cout << GetChange (coinset_1, coinset_1.size(), coin1) << endl;
cout << GetChange (coinset_2, coinset_2.size(), coin2) << endl;
cout << GetChange (coinset_3, coinset_3.size(), coin3) << endl;

return 0;
}
``````

Output

``````Number of ways of making coin change using dynamic programming
4
3
4
Number of ways of making coin change using recursion
4
3
4
``````