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

Q: What is Python Program for Coin Change using the Space Optimized 1D array?

In this article, we will learn Python Program for Coin Change using the Space Optimized 1D array,This free Python tutorial for complete beginners will help you learn Python from scratch.

Q: How to use Python Program for Coin Change using the Space Optimized 1D array in Python?

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.

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

In the above tabulation approach we are only using dp[i-1][j] and dp[i][j] etc, so we can do space optimization by only using a 1d dp array.

Step-by-step approach:

Create a 1D dp array, dp[i] represents the number of ways to make the sum i using the given coin denominations.
The outer loop iterates over the coins, and the inner loop iterates over the target sums. For each dp[j], it calculates the number of ways to make change using the current coin denomination and the previous results stored in dp.
dp[sum] contains the total number of ways to make change for the given target sum using the available coin denominations. This approach optimizes space by using a 1D array instead of a 2D DP table.

Below is the implementation of the above approach:

Python

# Dynamic Programming Python implementation of Coin
# Change problem
 
 
def count(coins, n, sum):
 
    # dp[i] will be storing the number of solutions for
    # value i. We need sum+1 rows as the dp is constructed
    # in bottom up manner using the base case (sum = 0)
    # Initialize all table values as 0
    dp = [0 for k in range(sum+1)]
 
    # Base case (If given value is 0)
    dp[0] = 1
 
    # Pick all coins one by one and update the dp[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for i in range(0, n):
        for j in range(coins[i], sum+1):
            dp[j] += dp[j-coins[i]]
 
    return dp[sum]
 
 
# Driver program to test above function
coins = [1, 2, 3]
n = len(coins)
sum = 5
x = count(coins, n, sum)
print(x)
 
# This code is contributed by Afzal Ansari

Output

Time complexity : O(N*sum)
Auxiliary Space : O(sum)

Please refer complete article on Coin Change | DP-7 for more details!

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