Python Program for Coin Change using Dynamic Programming (Memoization)

Q: What is Python Program for Coin Change using Dynamic Programming (Memoization)?

In this article, we will learn Python Program for Coin Change using Dynamic Programming (Memoization),This free Python tutorial for complete beginners will help you learn Python from scratch.

Python Program for Coin Change using Recursion:

Python Program for Coin Change using Dynamic Programming (Tabulation):

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

Output

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}.