Problem Description

You have an array coins that contains integers representing different coin denominations (like 1 cent, 5 cents, 25 cents, etc.). You also have a target amount that represents the total amount of money you need to make.

Your task is to find the minimum number of coins needed to make exactly that amount. You can use each type of coin as many times as you want (infinite supply of each coin denomination).

If it's impossible to make the exact amount with the given coins, return -1.

For example:

• If coins = [1, 2, 5] and amount = 11, the minimum number of coins is 3 (using two 5-cent coins and one 1-cent coin: 5 + 5 + 1 = 11)
• If coins = [2] and amount = 3, it's impossible to make exactly 3 with only 2-cent coins, so return -1

The solution uses dynamic programming with a 2D table f[i][j] where:

• i represents using the first i types of coins
• j represents the target amount
• f[i][j] stores the minimum number of coins needed

The key state transition is: f[i][j] = min(f[i-1][j], f[i][j-x] + 1), which means:

• Either don't use the current coin type (take f[i-1][j])
• Or use one of the current coin and look up the solution for the remaining amount (f[i][j-x] + 1)

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: We can model this problem as a graph where each node represents an amount of money, and edges represent using a coin to transition from one amount to another.

Is it a tree?

• No: This is not a tree structure because multiple paths can lead to the same amount (e.g., reaching amount 3 using [1,1,1] or [1,2]).

Is the problem related to directed acyclic graphs?

• No: The graph can have cycles (we can use the same coin multiple times).

Is the problem related to shortest paths?

• Yes: We're looking for the minimum (shortest) number of coins (steps) to reach the target amount from 0.

Is the graph Weighted?

• No: Each edge has the same weight of 1 (using one coin counts as one step).

BFS

• Yes: Since we have an unweighted graph shortest path problem, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the minimum number of coins needed. In the BFS approach, we start from amount 0 and explore all possible amounts we can reach by adding one coin at a time, level by level, until we reach the target amount. The first time we reach the target amount gives us the minimum number of coins needed.

Intuition

Think of this problem as finding the shortest path in a graph. Imagine you're at amount 0, and you want to reach the target amount. Each coin represents a way to "jump" forward by its value. The question becomes: what's the minimum number of jumps needed to reach exactly the target?

This naturally leads us to think about BFS because:

1. We want the minimum number of steps (coins)
2. Each step has equal weight (using any coin counts as 1 coin used)
3. We explore all possibilities level by level

However, the provided solution uses Dynamic Programming instead of BFS. Why? While BFS would work, DP is more efficient here because:

The problem has optimal substructure: If we know the minimum coins needed for amount j-x (where x is a coin value), then for amount j, we just need one more coin of value x. This gives us f[j] = f[j-x] + 1.

The problem also has overlapping subproblems: To calculate the minimum coins for amount 11, we might need to know the answer for amount 6 (if we use a 5-coin). But amount 6 might also be needed when calculating amount 7 (if we use a 1-coin). Instead of recalculating, we store and reuse these results.

The 2D DP approach f[i][j] represents: "What's the minimum coins needed to make amount j using only the first i types of coins?" For each coin type and amount combination, we have two choices:

• Don't use this coin type at all: f[i-1][j]
• Use at least one of this coin: f[i][j-x] + 1

We take the minimum of these choices. The beauty is that f[i][j-x] already contains the optimal solution for using the same coin multiple times (unbounded knapsack property), avoiding the need to explicitly enumerate how many coins of each type to use.

Solution Approach

The solution implements the Complete Knapsack variant of Dynamic Programming. Let's walk through the implementation step by step:

1. Initialize the DP Table:

f = [[inf] * (n + 1) for _ in range(m + 1)]
f[0][0] = 0

• Create a 2D table f[i][j] where i ranges from 0 to m (number of coin types) and j ranges from 0 to n (target amount)
• f[i][j] represents the minimum coins needed to make amount j using the first i types of coins
• Initialize all values to infinity (impossible), except f[0][0] = 0 (0 coins needed to make amount 0)

2. Fill the DP Table:

for i, x in enumerate(coins, 1):
    for j in range(n + 1):
        f[i][j] = f[i - 1][j]
        if j >= x:
            f[i][j] = min(f[i][j], f[i][j - x] + 1)

For each coin type i with value x:

• For each amount j from 0 to n:
  • First, inherit the solution without using this coin: f[i][j] = f[i-1][j]
  • If the current amount j is at least the coin value x, we can consider using this coin:
    • f[i][j - x] + 1 means: take the minimum coins for amount (j - x) using coins up to type i, then add 1 more coin of value x
    • Take the minimum between not using and using this coin

3. State Transition Formula:

The key insight is the state transition: f[i][j] = min(f[i-1][j], f[i][j-x] + 1)

This elegantly handles the unbounded knapsack nature because:

• f[i-1][j]: Don't use coin type i at all
• f[i][j-x] + 1: Use at least one coin of type i. Note that we use f[i][j-x] not f[i-1][j-x], which means we can use the same coin type multiple times

4. Return the Result:

return -1 if f[m][n] >= inf else f[m][n]

• If f[m][n] is still infinity, it's impossible to make the exact amount, return -1
• Otherwise, return the minimum number of coins needed

Time Complexity: O(m * n) where m is the number of coin types and n is the target amount
Space Complexity: O(m * n) for the 2D DP table

Example Walkthrough

Let's walk through a concrete example with coins = [1, 2, 5] and amount = 7.

We'll build a 2D DP table f[i][j] where:

• Rows (i): represent using the first i coin types (0 to 3)
• Columns (j): represent the target amount (0 to 7)

Initial Setup:

Coins: [1, 2, 5]
Amount: 7

Initialize f[4][8] with all infinity, except f[0][0] = 0

Step-by-step DP Table Construction:

Row 0 (using no coins):

Amount:  0   1   2   3   4   5   6   7
f[0][j]: 0   ∞   ∞   ∞   ∞   ∞   ∞   ∞

Row 1 (using coin value 1):

• For j=0: f[1][0] = f[0][0] = 0
• For j=1: f[1][1] = min(f[0][1], f[1][0]+1) = min(∞, 0+1) = 1
• For j=2: f[1][2] = min(f[0][2], f[1][1]+1) = min(∞, 1+1) = 2
• For j=3: f[1][3] = min(f[0][3], f[1][2]+1) = min(∞, 2+1) = 3
• Continue this pattern...

Amount:  0   1   2   3   4   5   6   7
f[1][j]: 0   1   2   3   4   5   6   7

Row 2 (using coins 1 and 2):

• For j=0: f[2][0] = f[1][0] = 0
• For j=1: f[2][1] = f[1][1] = 1 (can't use coin 2, j < 2)
• For j=2: f[2][2] = min(f[1][2], f[2][0]+1) = min(2, 0+1) = 1
• For j=3: f[2][3] = min(f[1][3], f[2][1]+1) = min(3, 1+1) = 2
• For j=4: f[2][4] = min(f[1][4], f[2][2]+1) = min(4, 1+1) = 2
• Continue this pattern...

Amount:  0   1   2   3   4   5   6   7
f[2][j]: 0   1   1   2   2   3   3   4

Row 3 (using coins 1, 2, and 5):

• For j=0-4: Same as f[2][j] (can't use coin 5 for amounts < 5)
• For j=5: f[3][5] = min(f[2][5], f[3][0]+1) = min(3, 0+1) = 1
• For j=6: f[3][6] = min(f[2][6], f[3][1]+1) = min(3, 1+1) = 2
• For j=7: f[3][7] = min(f[2][7], f[3][2]+1) = min(4, 1+1) = 2

Amount:  0   1   2   3   4   5   6   7
f[3][j]: 0   1   1   2   2   1   2   2

Final Answer: f[3][7] = 2

This means we need minimum 2 coins to make amount 7. The actual coins would be [5, 2] (one 5-coin and one 2-coin).

Key Observations:

1. When processing coin value 2, we improved solutions for even amounts (j=2,4,6)
2. When processing coin value 5, we dramatically improved j=5 from 3 coins to just 1 coin
3. The formula f[i][j-x] + 1 allows us to reuse the same coin type multiple times (notice how f[2][4] uses f[2][2], allowing two 2-coins)

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of types of coins and n is the total amount. This is because we have two nested loops: the outer loop iterates through all m coins (from index 1 to m), and the inner loop iterates through all possible amounts from 0 to n. Each cell f[i][j] is computed exactly once with constant time operations.

The space complexity is O(m × n). We create a 2D DP table f with dimensions (m + 1) × (n + 1) to store the minimum number of coins needed for each subproblem. The table has (m + 1) rows representing different coin combinations (0 to m coins) and (n + 1) columns representing different target amounts (0 to n).

Common Pitfalls

1. Incorrect Base Case Initialization

A common mistake is only initializing dp[0][0] = 0 but forgetting that we can make amount 0 with any subset of coins (by using 0 coins). This leads to incorrect results.

Incorrect:

dp = [[float('inf')] * (amount + 1) for _ in range(num_coins + 1)]
dp[0][0] = 0  # Only this is initialized

Correct:

dp = [[float('inf')] * (amount + 1) for _ in range(num_coins + 1)]
# Initialize all dp[i][0] = 0 (0 coins needed for amount 0)
for i in range(num_coins + 1):
    dp[i][0] = 0

2. Using Wrong DP State in Transition

When considering using a coin, some people mistakenly use dp[coin_idx - 1][current_amount - current_coin_value] + 1 instead of dp[coin_idx][current_amount - current_coin_value] + 1. This error treats the problem as a 0/1 knapsack (each coin used at most once) rather than an unbounded knapsack.

Incorrect:

# This assumes each coin can only be used once
dp[coin_idx][current_amount] = min(
    dp[coin_idx][current_amount],
    dp[coin_idx - 1][current_amount - current_coin_value] + 1  # Wrong!
)

Correct:

# This allows unlimited use of each coin type
dp[coin_idx][current_amount] = min(
    dp[coin_idx][current_amount],
    dp[coin_idx][current_amount - current_coin_value] + 1  # Correct!
)

3. Space Optimization Gone Wrong

When optimizing to 1D array, a common mistake is updating values in the wrong order, causing previously computed values to be overwritten before they're used.

Incorrect 1D optimization:

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
    for j in range(amount + 1):  # Wrong order!
        if j >= coin:
            dp[j] = min(dp[j], dp[j - coin] + 1)

Correct 1D optimization:

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
    for j in range(coin, amount + 1):  # Start from coin value
        dp[j] = min(dp[j], dp[j - coin] + 1)

4. Integer Overflow with Large Values

Using a very large number like sys.maxsize for infinity can cause integer overflow when adding 1 to it.

Problematic:

import sys
dp = [[sys.maxsize] * (amount + 1) for _ in range(num_coins + 1)]
# Later: dp[i][j] = dp[i][j - coin] + 1  # Could overflow!

Better approach:

# Use float('inf') or a reasonable upper bound
dp = [[float('inf')] * (amount + 1) for _ in range(num_coins + 1)]
# OR
MAX_COINS = amount + 1  # Maximum possible coins needed (all 1-cent coins)
dp = [[MAX_COINS] * (amount + 1) for _ in range(num_coins + 1)]

5. Off-by-One Errors in Index Mapping

Confusion between 0-indexed arrays and 1-indexed logic can lead to accessing wrong coin values.

Incorrect:

for coin_idx in range(1, num_coins + 1):
    current_coin_value = coins[coin_idx]  # IndexError or wrong coin!

Correct:

for coin_idx in range(1, num_coins + 1):
    current_coin_value = coins[coin_idx - 1]  # Correct mapping