How can you implement the coin change problem using memoization?

1 The coin change problem

The coin change problem asks how many ways you can make a given amount of money using a set of coins with different denominations. For instance, if you have coins of 1, 2, and 5 units, and you want to make 7 units, you can do it in six distinct ways. To solve the coin change problem recursively, consider two cases for each coin: use it or don't. If you use it, reduce the amount by the value of the coin and repeat the process with the same set of coins. Alternatively, if you don't use it, exclude the coin and repeat the process with the remaining coins. The base cases are when the amount is zero (one way to make change) or negative (no way to make change).

2 The memoization technique

The recursive solution to the coin change problem is simple but inefficient, because it repeats many subproblems that have the same amount and coins. For example, if you want to make 7 units with coins of 1, 2, and 5, you will compute the number of ways to make 5 units with coins of 1 and 2 twice: once when you use the 2 coin and once when you don't.

The memoization technique can improve the performance of the recursive solution by storing the results of subproblems in a cache and retrieving them when needed. The cache can be implemented as a two-dimensional array, where the rows represent the amounts and the columns represent the coins. The value at each cell is the number of ways to make the corresponding amount with the corresponding coins. Initially, the cache is filled with -1 to indicate that the subproblems are not solved yet.

3 The memoized solution

The memoized solution to the coin change problem is similar to the recursive solution, except that it checks the cache before computing the subproblems. If the cache contains a valid value for the subproblem, it returns it without further computation. Otherwise, it computes the subproblem recursively and stores the result in the cache for future use.

The memoized solution can be implemented in Python as follows:

# Define the coins and the amount
coins = [1, 2, 5]
amount = 7
# Initialize the cache with -1
cache = [[-1 for _ in range(len(coins))] for _ in range(amount + 1)]
# Define the memoized function
def coin_change_memo(amount, coins, index, cache):
  # Base cases
  if amount == 0:
    return 1
  if amount < 0 or index < 0:
    return 0
  
  # Check the cache
  if cache[amount][index] != -1:
    return cache[amount][index]
  
  # Recursive cases
  # Use the coin
  use = coin_change_memo(amount - coins[index], coins, index, cache)
  # Don't use the coin
  skip = coin_change_memo(amount, coins, index - 1, cache)
  # Store and return the result
  cache[amount][index] = use + skip
  return cache[amount][index]
# Call the memoized function
print(coin_change_memo(amount, coins, len(coins) - 1, cache))        

The memoized solution has a time complexity of O(amount * len(coins)) and a space complexity of O(amount * len(coins)), which are both better than the recursive solution, which has a time complexity of O(2^(amount + len(coins))) and a space complexity of O(amount + len(coins)).