Python Program for Coin Change using Dynamic Programming (Memoization)
The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So 2D array can be used to store results of previously solved subproblems.
Step-by-step approach:
- Create a 2D dp array to store the results of previously solved subproblems.
- dp[i][j] will represent the number of distinct ways to make the sum j by using the first i coins.
- During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.
Below is the implementation of the above approach:
Python3
# Python program for the above approach # Recursive function to count the numeber of distinct ways # to make the sum by using n coins def count(coins, sum , n, dp): # Base Case if ( sum = = 0 ): dp[n][ sum ] = 1 return dp[n][ sum ] # If number of coins is 0 or sum is less than 0 then there is no way to make the sum. if (n = = 0 or sum < 0 ): return 0 # If the subproblem is previously calculated then simply return the result if (dp[n][ sum ] ! = - 1 ): return dp[n][ sum ] # Two options for the current coin dp[n][ sum ] = count(coins, sum - coins[n - 1 ], n, dp) + \ count(coins, sum , n - 1 , dp) return dp[n][ sum ] # Driver code if __name__ = = '__main__' : tc = 1 while (tc ! = 0 ): n = 3 sum = 5 coins = [ 1 , 2 , 3 ] dp = [[ - 1 for i in range ( sum + 1 )] for j in range (n + 1 )] res = count(coins, sum , n, dp) print (res) tc - = 1 |
5
Time Complexity: O(N*sum), where N is the number of coins and sum is the target sum.
Auxiliary Space: O(N*sum)
Python Program for Coin Change | DP-7
Write a Python program for a given integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to find the number of ways to make a sum by using different denominations.
Examples:
Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}.Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
Contact Us