coin change Algorithm
The advent of paper money in the mid-17th century and the development of modern banking and floating exchange rates in the 20th century allowed a foreign exchange market to develop. This provided a manner for banks and other specialist fiscal company such as bureaux de change and forex brokers to easily change one state's money for another, and with the added confidence of transparency.
When outsiders, particularly traveling merchants, visited towns for a market fair, it became necessary to exchange foreign coins to local ones at local money changers. The merchant could then withdraw the money in local currency to conduct trade or, more likely, keep it deposited: the money changer would act as a clearing facility. In ancient times in Jerusalem, pilgrims visiting the Jewish Temple on Jewish Holy day would change some of their money from the standard Greek and Roman currency for Jewish and Tyrian money,
//
// A Stack is an abstract data type that serves as a collection
// of elements, with two principal operations are push & pop
//
// The All ▲lgorithms library for python
//
// https://allalgorithms.com/dynamic-programming/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Nikunj Taneja
// Github: @underscoreorcus
//
#include<iostream>
using namespace std;
int count( int S[], int m, int n )
{
int i, j, x, y;
// We need n+1 rows as the table is constructed
// in bottom up manner using the base case 0
// value case (n = 0)
int table[n+1][m];
// Fill the enteries for 0 value case (n = 0)
for (i=0; i<m; i++)
table[0][i] = 1;
// Fill rest of the table entries in bottom
// up manner
for (i = 1; i < n+1; i++)
{
for (j = 0; j < m; j++)
{
// Count of solutions including S[j]
x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
// Count of solutions excluding S[j]
y = (j >= 1)? table[i][j-1]: 0;
table[i][j] = x + y;
}
}
return table[n][m-1];
}
int main()
{
int coins[] = {1, 2, 3};
int m = sizeof(coins)/sizeof(int);
int n = 5;
cout << count(coins, m, n);
return 0;
}
