DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences

Introduction

This tutorial provides a step-by-step guide to solving the Coin Change problem using dynamic programming techniques. We will explore memoization, tabulation, and space optimization methods, focusing on how to count the number of ways to make a certain amount using an infinite supply of different coin denominations. This problem is essential in understanding dynamic programming concepts, especially in subsequence patterns.

Step 1: Understand the Problem

Before diving into solutions, clarify what the Coin Change problem entails:

• You are given a set of coin denominations and a target amount.
• Your goal is to determine how many ways you can combine those coins to reach the target amount.
• Each coin can be used an infinite number of times.

Step 2: Set Up the Problem

To effectively solve the problem, establish the following:

• Define the input parameters:
  • coins: an array of coin denominations.
  • amount: the total amount to achieve.

Example:

coins = [1, 2, 3]
amount = 4

Step 3: Implement Memoization

Memoization involves storing previously computed results to avoid redundant calculations:

1. Create a recursive function that takes the current amount and the index of the coin.
2. Use a memoization table (array or dictionary) to store results for specific amounts.
3. The base cases are:
   • If the amount is 0, return 1 (one way to make zero).
   • If the amount is negative or no coins are left, return 0.

Example code:

def coin_change_memo(coins, amount, index, memo):
    if amount == 0:
        return 1
    if amount < 0 or index < 0:
        return 0
    if (amount, index) in memo:
        return memo[(amount, index)]
    
    memo[(amount, index)] = (coin_change_memo(coins, amount, index, memo) +
                             coin_change_memo(coins, amount - coins[index], index, memo))
    return memo[(amount, index)]

Step 4: Implement Tabulation

Tabulation is a bottom-up approach that builds a table of results:

1. Create a 2D array dp where dp[i][j] represents the number of ways to make amount j using the first i coins.
2. Initialize the first column (amount 0) to 1 since there is one way to make zero.
3. Fill the table iteratively:
   • For each coin, and for each amount, update the table based on whether to include the coin or not.

Example code:

def coin_change_tabulation(coins, amount):
    dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
    for i in range(len(coins) + 1):
        dp[i][0] = 1  # One way to make zero
    
    for i in range(1, len(coins) + 1):
        for j in range(1, amount + 1):
            dp[i][j] = dp[i - 1][j]  # Exclude coin
            if j >= coins[i - 1]:
                dp[i][j] += dp[i][j - coins[i - 1]]  # Include coin

    return dp[len(coins)][amount]

Step 5: Optimize Space Complexity

For further optimization, reduce the space complexity to O(amount) using a single array:

1. Use a one-dimensional array dp instead of a 2D array.
2. Iterate through coins and update the dp array in-place.

Example code:

def coin_change_space_optimized(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make zero
    
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]

    return dp[amount]

Conclusion

In this tutorial, we learned how to solve the Coin Change problem using dynamic programming techniques including memoization, tabulation, and space optimization. Understanding these methods enhances your skills in dynamic programming and prepares you for related coding challenges.

Next steps include practicing these implementations with different coin sets and amounts, exploring further dynamic programming problems, and reviewing the provided lecture notes for more in-depth understanding.