Python Program for Coin Change using Dynamic Programming (Tabulation)

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

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

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

Python Program for Coin Change using the Space Optimized 1D array:

Create a 2D dp array with rows and columns equal to the number of coin denominations and target sum.

dp[0][0] will be set to 1 which represents the base case where the target sum is 0, and there is only one way to make the change by not selecting any coin.

Iterate through the rows of the dp array (i from 1 to n), representing the current coin being considered.

The inner loop iterates over the target sums (j from 0 to sum).

Add the number of ways to make change without using the current coin, i.e., dp[i][j] += dp[i-1][j].

Add the number of ways to make change using the current coin, i.e., dp[i][j] += dp[i][j-coins[i-1]].

dp[n][sum] will contain the total number of ways to make change for the given target sum using the available coin denominations.

Below is the implementation of the above approach:

Python3

# Function to calculate the total distinct ways to make a sum using n coins of different denominations
def count(coins, n, target_sum):
    # 2D dp array where n is the number of coin denominations and target_sum is the target sum
    dp = [[0 for j in range(target_sum + 1)] for i in range(n + 1)]
 
    # Represents the base case where the target sum is 0, and there is only one way to make change: by not selecting any coin
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(target_sum + 1):
            # Add the number of ways to make change without using the current coin
            dp[i][j] += dp[i - 1][j]
 
            if j - coins[i - 1] >= 0:
                # Add the number of ways to make change using the current coin
                dp[i][j] += dp[i][j - coins[i - 1]]
 
    return dp[n][target_sum]
 
# Driver Code
if __name__ == "__main__":
    coins = [1, 2, 3]
    n = 3
    target_sum = 5
    print(count(coins, n, target_sum))

Output

Time complexity : O(N*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}.