Coin Change Problem
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
- Optimal Substructure
To count total number solutions, we can divide all set solutions in two sets.- Solutions that do not contain mth coin (or Sm).
- Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).
Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.
[ad type=”banner”]- Overlapping Subproblems
Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above using Python code.
Implementation of Coin change using Python:
[pastacode lang=”python” manual=”%0A%23%20Recursive%20Python3%20program%20for%20%0A%23%20coin%20change%20problem.%20%0A%20%20%0A%23%20Returns%20the%20count%20of%20ways%20we%20can%20sum%20%0A%23%20S%5B0…m-1%5D%20coins%20to%20get%20sum%20n%20%0Adef%20count(S%2C%20m%2C%20n%20)%3A%20%0A%20%20%0A%20%20%20%20%23%20If%20n%20is%200%20then%20there%20is%201%20%0A%20%20%20%20%23%20solution%20(do%20not%20include%20any%20coin)%20%0A%20%20%20%20if%20(n%20%3D%3D%200)%3A%20%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%0A%20%20%20%20%23%20If%20n%20is%20less%20than%200%20then%20no%20%0A%20%20%20%20%23%20solution%20exists%20%0A%20%20%20%20if%20(n%20%3C%200)%3A%20%0A%20%20%20%20%20%20%20%20return%200%3B%20%0A%20%20%0A%20%20%20%20%23%20If%20there%20are%20no%20coins%20and%20n%20%0A%20%20%20%20%23%20is%20greater%20than%200%2C%20then%20no%20%0A%20%20%20%20%23%20solution%20exist%20%0A%20%20%20%20if%20(m%20%3C%3D0%20and%20n%20%3E%3D%201)%3A%20%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%0A%20%20%20%20%23%20count%20is%20sum%20of%20solutions%20(i)%20%20%0A%20%20%20%20%23%20including%20S%5Bm-1%5D%20(ii)%20excluding%20S%5Bm-1%5D%20%0A%20%20%20%20return%20count(%20S%2C%20m%20-%201%2C%20n%20)%20%2B%20count(%20S%2C%20m%2C%20n-S%5Bm-1%5D%20)%3B%20%0A%20%20%0A%23%20Driver%20program%20to%20test%20above%20function%20%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%20%0Am%20%3D%20len(arr)%20%0Aprint(count(arr%2C%20m%2C%204))%20″ message=”Python” highlight=”” provider=”manual”/]It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for S = {1, 2, 3} and n = 5.
The function C({1}, 3) is called two times. If we draw the complete tree, then we can see that there are many subproblems being called more than once.
C() --> count()
C({1,2,3}, 5)
/ \
/ \
C({1,2,3}, 2) C({1,2}, 5)
/ \ / \
/ \ / \
C({1,2,3}, -1) C({1,2}, 2) C({1,2}, 3) C({1}, 5)
/ \ / \ / \
/ \ / \ / \
C({1,2},0) C({1},2) C({1,2},1) C({1},3) C({1}, 4) C({}, 5)
/ \ / \ / \ / \
/ \ / \ / \ / \
. . . . . . C({1}, 3) C({}, 4)
/ \
/ \
. .
Since same suproblems are called again, this problem has Overlapping Subproblems property. So the Coin Change problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.
[ad type=”banner”]Dynamic Programming Solution
[pastacode lang=”python” manual=”%23%20Dynamic%20Programming%20Python%20implementation%20of%20Coin%20Change%20problem%0Adef%20count(S%2C%20m%2C%20n)%3A%0A%20%20%20%20%23%20We%20need%20n%2B1%20rows%20as%20the%20table%20is%20consturcted%20in%20bottom%20up%0A%20%20%20%20%23%20manner%20using%20the%20base%20case%200%20value%20case%20(n%20%3D%200)%0A%20%20%20%20table%20%3D%20%5B%5B0%20for%20x%20in%20range(m)%5D%20for%20x%20in%20range(n%2B1)%5D%0A%20%0A%20%20%20%20%23%20Fill%20the%20enteries%20for%200%20value%20case%20(n%20%3D%200)%0A%20%20%20%20for%20i%20in%20range(m)%3A%0A%20%20%20%20%20%20%20%20table%5B0%5D%5Bi%5D%20%3D%201%0A%20%0A%20%20%20%20%23%20Fill%20rest%20of%20the%20table%20enteries%20in%20bottom%20up%20manner%0A%20%20%20%20for%20i%20in%20range(1%2C%20n%2B1)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(m)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Count%20of%20solutions%20including%20S%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20table%5Bi%20-%20S%5Bj%5D%5D%5Bj%5D%20if%20i-S%5Bj%5D%20%3E%3D%200%20else%200%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Count%20of%20solutions%20excluding%20S%5Bj%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20y%20%3D%20table%5Bi%5D%5Bj-1%5D%20if%20j%20%3E%3D%201%20else%200%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20total%20count%0A%20%20%20%20%20%20%20%20%20%20%20%20table%5Bi%5D%5Bj%5D%20%3D%20x%20%2B%20y%0A%20%0A%20%20%20%20return%20table%5Bn%5D%5Bm-1%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%0Am%20%3D%20len(arr)%0An%20%3D%204%0Aprint(count(arr%2C%20m%2C%20n))%0A%20″ message=”Python” highlight=”” provider=”manual”/]Output:
4
Time Complexity: O(mn)
Following is a simplified version of method 2. The auxiliary space required here is O(n) only.
[pastacode lang=”python” manual=”%23%20Dynamic%20Programming%20Python%20implementation%20of%20Coin%20%0A%23%20Change%20problem%0Adef%20count(S%2C%20m%2C%20n)%3A%0A%20%0A%20%20%20%20%23%20table%5Bi%5D%20will%20be%20storing%20the%20number%20of%20solutions%20for%0A%20%20%20%20%23%20value%20i.%20We%20need%20n%2B1%20rows%20as%20the%20table%20is%20constructed%0A%20%20%20%20%23%20in%20bottom%20up%20manner%20using%20the%20base%20case%20(n%20%3D%200)%0A%20%20%20%20%23%20Initialize%20all%20table%20values%20as%200%0A%20%20%20%20table%20%3D%20%5B0%20for%20k%20in%20range(n%2B1)%5D%0A%20%0A%20%20%20%20%23%20Base%20case%20(If%20given%20value%20is%200)%0A%20%20%20%20table%5B0%5D%20%3D%201%0A%20%0A%20%20%20%20%23%20Pick%20all%20coins%20one%20by%20one%20and%20update%20the%20table%5B%5D%20values%0A%20%20%20%20%23%20after%20the%20index%20greater%20than%20or%20equal%20to%20the%20value%20of%20the%0A%20%20%20%20%23%20picked%20coin%0A%20%20%20%20for%20i%20in%20range(0%2Cm)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(S%5Bi%5D%2Cn%2B1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20table%5Bj%5D%20%2B%3D%20table%5Bj-S%5Bi%5D%5D%0A%20%0A%20%20%20%20return%20table%5Bn%5D%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aarr%20%3D%20%5B1%2C%202%2C%203%5D%0Am%20%3D%20len(arr)%0An%20%3D%204%0Ax%20%3D%20count(arr%2C%20m%2C%20n)%0Aprint%20(x)%0A%20″ message=”Python” highlight=”” provider=”manual”/]Output:
4[ad type=”banner”]