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,
"""
You have m types of coins available in infinite quantities
where the value of each coins is given in the array S=[S0,... Sm-1]
Can you determine number of ways of making change for n units using
the given types of coins?
https://www.hackerrank.com/challenges/coin-change/problem
"""
def dp_count(S, m, n):
"""
>>> dp_count([1, 2, 3], 3, 4)
4
>>> dp_count([1, 2, 3], 3, 7)
8
>>> dp_count([2, 5, 3, 6], 4, 10)
5
>>> dp_count([10], 1, 99)
0
>>> dp_count([4, 5, 6], 3, 0)
1
"""
# table[i] represents the number of ways to get to amount i
table = [0] * (n + 1)
# There is exactly 1 way to get to zero(You pick no coins).
table[0] = 1
# Pick all coins one by one and update table[] values
# after the index greater than or equal to the value of the
# picked coin
for coin_val in S:
for j in range(coin_val, n + 1):
table[j] += table[j - coin_val]
return table[n]
if __name__ == "__main__":
import doctest
doctest.testmod()
