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:
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
Output:
4
Time Complexity: O(mn)
Following is a simplified version of method 2. The auxiliary space required here is O(n) only.
Output:
4[ad type=”banner”]