Dynamic Programming for Coin Change

1. Coin Change: Minimum Number of Coins

This is one of the most classic dynamic programming problems.

Problem: Given an array of coin denominations and a total amount, find the fewest number of coins required to make up that amount. If it's impossible, return -1. You have an infinite supply of each coin.

This is LeetCode 322 and is a clear example of an Unbounded Knapsack optimization problem:

• Knapsack Capacity (W): The target amount.
• Items: The coins.
• Item Weights: The coin denominations coin_value.
• Item Values: The value of each coin is simply 1, because we want to minimize the count of coins.

Why a Greedy Approach Fails

A natural first thought is to be greedy: always take the largest coin possible. For coins = [1, 5, 10, 25] and amount = 30, this works: 25 + 5. But what about coins = [1, 3, 4] and amount = 6?

• Greedy: Take 4. Remaining amount is 2. Can't use 3 or 4. So we take 1 twice. Total: 4 + 1 + 1 (3 coins).
• Optimal: Take 3 twice. Total: 3 + 3 (2 coins).

The greedy approach fails. We must explore all combinations, which points us to dynamic programming.

The Bottom-Up DP Solution

We can solve this by building up a solution for every amount from 1 up to our target. Let dp[i] be the minimum number of coins needed to make amount i.

• State: dp[i] = minimum coins for amount i.

• Initialization: We create a dp array of size amount + 1. We can initialize all values to a stand-in for infinity (like amount + 1, since the answer can't be more than amount if a solution exists). We set dp[0] = 0, as it takes zero coins to make an amount of 0.

• Recurrence Relation: For each amount a from 1 to amount, we try every coin:
  If a >= coin, we have a potential new way to make a. The number of coins would be 1 (for the current coin) plus the minimum coins needed for the remaining amount, which is dp[a - coin]. We want the minimum over all possible coin choices.

  The recurrence for each amount a is:

  $$\text{dp}[a]=\min (\text{dp}[a],1+\text{dp}[a-\text{coin}])\text{for each coin in coins}$$

The following video provides an excellent walkthrough of this entire thought process.

Complexity Analysis:

• Time Complexity: O(amount * num_coins). We have two nested loops: one iterating through amounts and one through coins.
• Space Complexity: O(amount) for our dp array.

2. Coin Change: Number of Combinations

Now, let's look at the second major variation: instead of finding the minimum, we need to count the total number of unique combinations.

Problem: Given an array of coin denominations and a total amount, find the number of combinations that make up that amount. You have an infinite supply of each coin.

This is LeetCode 518. It's an Unbounded Knapsack counting problem. The key challenge here is to count combinations, not permutations. For example, [1, 2] and [2, 1] should be counted as one combination.

The Bottom-Up DP Solution (Space-Optimized)

To avoid counting permutations, we build our solution one coin at a time.
Let dp[j] be the number of ways to make amount j using the coins we have considered so far.

We iterate through the coins one by one. For each coin, we update the dp array for all amounts that this coin can contribute to.

• State: dp[j] = number of ways to make amount j.

• Initialization: We create a dp array of size amount + 1 initialized to all zeros. dp[0] is set to 1, because there is exactly one way to make an amount of 0: by choosing no coins. This is our crucial base case.

• Recurrence Relation:
  We use a nested loop structure:

  1. Outer Loop: Iterate through each coin in coins.
  2. Inner Loop: Iterate through each amount j from coin up to amount.

  For each j, we can form it by adding the current coin to any combination that formed j - coin. So, we update dp[j] by adding the number of ways we could form j - coin.

  $$\text{dp}[j]=\text{dp}[j]+\text{dp}[j-\text{coin}]$$

This structure ensures we only count combinations. By processing one coin fully before moving to the next, we guarantee a fixed order of coins in our combinations (e.g., smaller denominations are always considered before larger ones).

This approach is best understood through a clear explanation.

# What does this code calculate?
dp = [0] * (amount + 1)
dp[0] = 1
for j in range(1, amount + 1):
    for coin in coins:
        if j >= coin:
            dp[j] += dp[j - coin]

Conclusion

Congratulations on completing the Dynamic Programming module! The Coin Change problems are not only practical applications of the Unbounded Knapsack pattern but also fundamental DP questions that test core problem-solving skills valued in interviews.

Key Takeaways:

• Two Main Variations:
  1. Minimum Coins (Optimization): Use min() to find the optimal solution. The recurrence is dp[a] = min(dp[a], 1 + dp[a - coin]).
  2. Number of Ways (Counting): Use addition to count all possible combinations. The recurrence is dp[j] += dp[j - coin].
• Pattern Recognition: Both problems are classic examples of Unbounded Knapsack, where items (coins) can be reused.
• Implementation Details Matter: The loop order in the combination counting problem is a subtle but critical detail that separates a correct solution (combinations) from an incorrect one (permutations).

Preview of the Next Lesson:

We are now moving on to a new major topic: Graph Traversal Algorithms. In the next lesson, we will lay the groundwork by learning how to represent graphs in code, specifically using adjacency lists and adjacency matrices. This will prepare us for implementing fundamental algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS).