Dynamic Programming: Coin Change

1. Defining the Problem

First, let's be precise about the problem statement.

You are given an array of coin denominations and a total amount. Your task is to find the fewest number of coins required to make up that amount. If it's impossible to make the amount, you should return -1. You can assume you have an infinite supply of each coin.

For example: coins = [1, 2, 5], amount = 11.
The answer is 3, because 5 + 5 + 1 = 11.

A common first instinct is to use a greedy approach: always take the largest coin possible. But this doesn't always work. The following video explains the problem and provides a clear counterexample showing why a greedy strategy fails.

The failure of the greedy approach tells us we need a more exhaustive method that considers all possibilities. This is where Dynamic Programming shines.

2. Formulating the DP Solution

As we've learned, DP is about breaking a problem down into smaller, overlapping subproblems.

Let's define our subproblem:
Let dp[i] be the minimum number of coins required to make an amount of i.

Our goal is to find dp[amount].

To find dp[i], we can think about the last coin we add to reach the sum i. Suppose we use a coin with value c. The number of coins would be 1 (for the coin c) plus the minimum number of coins needed to make the remaining amount, which is i - c. We already know this value—it's dp[i - c]!

Since we want the minimum number of coins, we must try this for every available coin and take the best (minimum) result. This gives us our recurrence relation:

$\text{dp}[i]={\min }_{c\in \text{coins, }c\le i}(1+\text{dp}[i-c])$

This formula is the heart of our solution. It says the minimum coins for amount i is the minimum of 1 + dp[i - c] over all usable coins c.

3. The Bottom-Up (Tabulation) Implementation

Now, let's apply the four-step tabulation process you learned in the previous lesson to implement this recurrence.

1. Create the Table: We need to find the minimum coins for every amount from 0 up to amount. So, we create a 1D array, dp, of size amount + 1.

2. Initialize Base Cases:

   • The base case is dp[0]. How many coins does it take to make an amount of 0? Zero coins. So, dp[0] = 0.
   • What about the other entries? Since we're looking for a minimum, we should initialize them to a value that represents infinity. A common technique in Python is to use float('inf'). Another clever trick is to use amount + 1, since it's impossible to use more than amount coins (in the case of all coins being of value 1). This avoids floating-point numbers.

3. Iterate and Fill: We'll build our table from dp[1] up to dp[amount]. For each amount i, we'll check every coin in our list.

   • For each amount from 1 to amount:
     • For each coin in coins:
       • If we can use this coin (i.e., amount >= coin), we have a potential new answer for dp[amount]: 1 + dp[amount - coin].
       • We update dp[amount] to be the minimum of its current value and this new potential answer.
         The formula in code becomes: dp[i] = min(dp[i], 1 + dp[i - coin]).

4. Return the Answer: The final answer is dp[amount]. If dp[amount] is still the "infinity" value we initialized it with, it means that amount could never be reached. In that case, we return -1.

The following video provides an excellent walkthrough of this bottom-up logic and shows how to translate it directly into Python code.

For a concise, text-based summary of the implementation, you can also refer to this guide.

4. A Manual Walkthrough

Let's trace the algorithm with a concrete example to make sure the process is clear.
Problem: coins = [1, 3, 4], amount = 6.

1. Table: Create dp of size 7.

2. Initialize: dp = [0, 7, 7, 7, 7, 7, 7] (using amount + 1 = 7 as infinity).

3. Iterate:

   • i = 1:
     • coin=1: dp[1] = min(7, 1 + dp[0]) = 1.
     • dp is now [0, 1, 7, 7, 7, 7, 7].
   • i = 2:
     • coin=1: dp[2] = min(7, 1 + dp[1]) = 2.
     • dp is now [0, 1, 2, 7, 7, 7, 7].
   • i = 3:
     • coin=1: dp[3] = min(7, 1 + dp[2]) = 3.
     • coin=3: dp[3] = min(3, 1 + dp[0]) = 1.
     • dp is now [0, 1, 2, 1, 7, 7, 7].
   • i = 4:
     • coin=1: dp[4] = min(7, 1 + dp[3]) = 2.
     • coin=3: dp[4] = min(2, 1 + dp[1]) = 2.
     • coin=4: dp[4] = min(2, 1 + dp[0]) = 1.
     • dp is now [0, 1, 2, 1, 1, 7, 7].
   • i = 5:
     • coin=1: dp[5] = min(7, 1 + dp[4]) = 2.
     • coin=3: dp[5] = min(2, 1 + dp[2]) = 3.
     • coin=4: dp[5] = min(2, 1 + dp[1]) = 2.
     • dp is now [0, 1, 2, 1, 1, 2, 7].
   • i = 6:
     • coin=1: dp[6] = min(7, 1 + dp[5]) = 3.
     • coin=3: dp[6] = min(3, 1 + dp[3]) = 2.
     • coin=4: dp[6] = min(2, 1 + dp[2]) = 3.
     • dp is now [0, 1, 2, 1, 1, 2, 2].

4. Answer: Return dp[6], which is 2. (The optimal combination is 3 + 3).

Conclusion

You have now thoroughly dissected the Coin Change problem and mastered its canonical bottom-up DP solution. This pattern of building up a 1D array to solve for a target value is extremely common in competitive programming.

Key Takeaways:

• The greedy approach fails for the general Coin Change problem, motivating the need for DP.
• The subproblem dp[i] represents the minimum coins needed for amount i.
• The recurrence dp[i] = min(1 + dp[i - coin]) allows us to build the solution for a larger amount from the solutions for smaller amounts.
• The tabulation implementation involves creating a DP array, initializing it with a base case (dp[0]=0) and an infinity value, and then filling it iteratively.
• The final answer requires checking if the target amount was reachable.

Up Next:
In the previous lesson, we briefly used the 0/1 Knapsack problem to illustrate 2D tabulation. In our next lesson, we will make that our primary focus. You'll learn how to formally set up and solve this classic problem, which involves making choices about items with both weights and values, using a 2D DP table. This will give you practice with problems where the state depends on more than one parameter.