Coin Change (Minimum Coins)

▶

Steps

setup

Initialize dp array

Create a dp array of size amount+1 (12) filled with infinity to represent unreachable amounts, except dp[0] which is 0 since zero coins are needed to make amount zero.

💡 Setting dp[0] = 0 anchors the solution, showing that no coins are needed to make amount zero.

Line:

dp = [float('inf')] * (amount + 1)
dp[0] = 0

💡 This initialization sets the base case and marks all other amounts as initially unreachable.

fill_cells

Start filling dp for amount = 1

We begin computing dp[1]. For each coin, check if it can be used to form amount 1 and update dp[1] accordingly.

💡 This step starts the main loop where we try to build solutions for each amount from 1 to 11.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 We will try each coin to see if it can improve the minimum coins needed for amount 1.

compare

Check coin 1 for amount 1

Coin 1 fits into amount 1. Update dp[1] = min(dp[1], 1 + dp[1-1]) = min(∞, 1 + dp[0]) = 1.

💡 Using coin 1 alone can make amount 1 with 1 coin, so dp[1] improves from infinity to 1.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 This shows how the dp array is updated when a coin can form the amount directly or via smaller amounts.

compare

Check coin 2 for amount 1

Coin 2 is larger than amount 1, so it cannot be used. dp[1] remains 1.

💡 Coins larger than the current amount are skipped because they cannot contribute.

Line:

if coin <= i:

💡 This step shows the algorithm's pruning of invalid coin choices.

compare

Check coin 5 for amount 1

Coin 5 is larger than amount 1, so it cannot be used. dp[1] remains 1.

💡 Again, coins too large for the current amount are ignored.

Line:

if coin <= i:

💡 This confirms the filtering of coins by size at each amount.

fill_cells

Start filling dp for amount = 2

Now compute dp[2]. For each coin, check if it can improve dp[2].

💡 We move to the next amount to build solutions incrementally.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 The algorithm tries all coins for amount 2 to find the minimum coins needed.

compare

Check coin 1 for amount 2

Coin 1 fits into amount 2. Update dp[2] = min(dp[2], 1 + dp[2-1]) = min(∞, 1 + dp[1]) = 2.

💡 Using coin 1 plus the best way to make amount 1 gives a solution for amount 2.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 This shows how the solution builds on previously computed dp values.

compare

Check coin 2 for amount 2

Coin 2 fits exactly into amount 2. Update dp[2] = min(dp[2], 1 + dp[2-2]) = min(2, 1 + dp[0]) = 1.

💡 Using coin 2 alone is better than two coins of 1, so dp[2] improves to 1.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 This step shows how the algorithm finds better solutions by trying all coins.

compare

Check coin 5 for amount 2

Coin 5 is larger than amount 2, so it cannot be used. dp[2] remains 1.

💡 Coins too large for the current amount are skipped.

Line:

if coin <= i:

💡 This confirms the pruning of invalid coins.

fill_cells

Fill dp for amounts 3 and 4

Compute dp[3] and dp[4]. For each amount, check all coins to update dp values.

💡 We continue building solutions incrementally for amounts 3 and 4.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 The algorithm tries all coins for each amount to find minimum coins needed.

compare

Check coins for amount 3

Check coins 1, 2, and 5 for amount 3. Only coins 1 and 2 fit. dp[3] remains infinity because dp[2] and dp[1] are known but dp[3] not updated yet.

💡 We check all coins to see if dp[3] can be improved.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 Shows dependency on smaller amounts and that some dp values remain infinity until updated.

fill_cells

Fill dp for amount 5

Compute dp[5]. For each coin, check if it can improve dp[5].

💡 Amount 5 is important because coin 5 can directly form it.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 We will see how coin 5 drastically improves dp[5].

compare

Check coins 1, 2, and 5 for amount 5

Check coin 1: dp[5] = min(dp[5], 1 + dp[4]) = infinity since dp[4] is infinity. Check coin 2: dp[5] = min(dp[5], 1 + dp[3]) = infinity since dp[3] is infinity. Check coin 5: dp[5] = min(dp[5], 1 + dp[0]) = 1, update dp[5].

💡 Only coin 5 improves dp[5] from infinity to 1.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 Shows how larger coins can provide better solutions directly.

fill_cells

Fill dp for amounts 6 to 9

Compute dp[6], dp[7], dp[8], and dp[9]. For each amount, check all coins to update dp values.

💡 We continue building solutions incrementally for amounts 6 to 9.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 The algorithm tries all coins for each amount to find minimum coins needed.

fill_cells

Fill dp for amount 10

Compute dp[10]. For each coin, check if it can improve dp[10].

💡 Amount 10 can be formed by two 5 coins or other combinations.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 We will see dp[10] updated to 2 using two 5 coins.

compare

Check coins for amount 10

Check coin 1: dp[10] = min(dp[10], 1 + dp[9]) = infinity since dp[9] is infinity. Check coin 2: dp[10] = min(dp[10], 1 + dp[8]) = infinity since dp[8] is infinity. Check coin 5: dp[10] = min(dp[10], 1 + dp[5]) = 2, update dp[10].

💡 Only coin 5 improves dp[10] from infinity to 2.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 Shows how larger coins can combine to form amounts efficiently.

fill_cells

Fill dp for amount 11

Finally, compute dp[11]. For each coin, check if it can improve dp[11].

💡 Amount 11 is the target; we want to find the minimum coins needed.

Line:

for i in range(1, amount + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], 1 + dp[i - coin])

💡 We will see dp[11] updated to 3 using coins 5, 5, and 1.

compare

Check coin 1 for amount 11

Coin 1 fits into amount 11. Update dp[11] = min(dp[11], 1 + dp[10]) = min(∞, 1 + 2) = 3.

💡 Using coin 1 plus dp[10] gives a solution with 3 coins.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 This shows how the final amount builds on previous results.

compare

Check coin 2 for amount 11

Coin 2 fits into amount 11. Update dp[11] = min(dp[11], 1 + dp[9]). dp[9] is infinity, so no update.

💡 dp[9] not computed, so no improvement.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 Shows dependency on smaller amounts.

compare

Check coin 5 for amount 11

Coin 5 fits into amount 11. Update dp[11] = min(dp[11], 1 + dp[6]). dp[6] is infinity, so no update.

💡 dp[6] not computed, so no improvement.

Line:

if coin <= i:
    dp[i] = min(dp[i], 1 + dp[i - coin])

💡 Shows dependency on smaller amounts.

reconstruct

Return final answer

The dp array is fully computed. The minimum coins needed for amount 11 is dp[11] = 3.

💡 Reading dp[amount] gives the final answer or -1 if unreachable.

Line:

return dp[amount] if dp[amount] != float('inf') else -1

💡 The algorithm successfully found the minimum coins needed.

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)  # STEP 1
    dp[0] = 0  # STEP 1
    for i in range(1, amount + 1):  # STEP 2
        for coin in coins:  # STEP 2
            if coin <= i:  # STEP 3
                dp[i] = min(dp[i], 1 + dp[i - coin])  # STEP 3
    return dp[amount] if dp[amount] != float('inf') else -1  # STEP 21

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3

📊

Coin Change (Minimum Coins) - Watch the Algorithm Execute, Step by Step

Watching the dp array update step-by-step reveals how the algorithm builds solutions from smaller amounts to larger amounts, making the abstract code concrete.

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[0] = 0 (base case)

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

Computing dp[1]

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[1] updated to 1

Item 1 - wt:2 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[1] unchanged

Item 2 - wt:5 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[1] unchanged

Item 0 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞

Computing dp[2]

Item 0 - wt:1 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	2	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[2] updated to 2

Item 1 - wt:2 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[2] updated to 1

Item 2 - wt:5 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[2] unchanged

Item 0 - wt:3 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	∞	∞	∞	∞	∞	∞	∞

Computing dp[3]

Item 2 - wt:5 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	∞	∞	∞	∞	∞	∞	∞

dp[3] unchanged

Item 0 - wt:5 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	∞	∞	∞	∞	∞	∞	∞

Computing dp[5]

Item 2 - wt:5 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	∞	∞

dp[5] updated to 1

Item 0 - wt:6 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	∞	∞

Computing dp[6]

Item 0 - wt:10 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	∞	∞

Computing dp[10]

Item 2 - wt:5 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	∞

dp[10] updated to 2

Item 0 - wt:11 val:∞

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	∞

Computing dp[11]

Item 0 - wt:1 val:3

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	3

dp[11] updated to 3

Item 1 - wt:2 val:3

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	3

dp[11] unchanged

Item 2 - wt:5 val:3

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	3

dp[11] unchanged

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	0	1	1	∞	∞	1	∞	∞	∞	∞	2	3

Answer: 3 coins

Key Takeaways

✓ The dp array builds solutions incrementally from smaller amounts to larger amounts.

This is hard to see from code alone because the dp updates happen inside nested loops without explicit visualization.

✓ Each dp[i] depends on dp[i - coin] for all coins that fit, showing the unbounded knapsack pattern.

Visualizing dependencies clarifies why order and coin choices matter.

✓ Larger coins can drastically improve dp values when they fit exactly, as seen with coin 5 at amounts 5 and 10.

This concrete example shows how the algorithm finds better solutions by trying all coins.

Practice

1. You are given a set of positive integers and need to partition it into two subsets such that the absolute difference of their sums is minimized. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that sorts and assigns elements alternately to subsets

B. Dynamic programming using a subset-sum style approach to find achievable sums

C. Divide and conquer by recursively splitting the array into halves

D. Sorting and then pairing elements from opposite ends to balance sums

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing the difference between sums of two subsets, which is a classic partition problem variant.

2. Step 2: Identify algorithmic pattern

   Greedy or divide-and-conquer approaches do not guarantee minimal difference. Dynamic programming, specifically subset-sum style DP, can find all achievable sums up to total_sum, enabling minimal difference calculation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP subset-sum approach guarantees optimal partition [OK]

Hint: Minimal difference requires subset-sum DP, not greedy [OK]

Common Mistakes:

• Assuming greedy or sorting suffices for minimal difference

2. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.

B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.

C. A depth-first search that tries all subsets without memoization.

D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.

2. Step 2: Identify algorithm that guarantees correctness

   Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP tracks all sums up to target -> correct [OK]

Hint: Subset sum requires DP to track achievable sums [OK]

Common Mistakes:

• Thinking greedy or sorting solves subset sum optimally

3. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 11: Using bisect_right to find compatible job index

B. Line 7: Creating ends array from job end times

C. Line 4: Sorting jobs by start time instead of end time

D. Line 14: Calculating dp[i] as max of take and skip

Solution

1. Step 1: Identify sorting criteria

   Jobs must be sorted by end time for binary search on ends array to work correctly.

2. Step 2: Check sorting line

   Line 4 sorts by start time, breaking DP dependencies and binary search correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]

Hint: Sort jobs by end time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Incorrect binary search bounds
• Ignoring dp base cases

4. The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: dp initialization without dp[0] = true

B. Line 6: Outer loop iterating over elements

C. Line 7: Inner loop iterating backwards from total_sum

D. Line 11: Returning difference using total_sum and w

Solution

1. Step 1: Check base case initialization

   dp[0] must be true to represent sum zero achievable with empty subset; missing this causes no sums to be marked achievable.

2. Step 2: Verify other lines

   Loops and return statement are correct; only missing dp[0] initialization breaks correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[0] = true, dp array never updates correctly [OK]

Hint: dp[0] = true is essential base case [OK]

Common Mistakes:

• Forgetting dp[0] initialization
• Using forward iteration causing overcounting

5. Suppose the problem changes so that you can use each item an unlimited number of times (unbounded knapsack). Which modification to the space-optimized bottom-up DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from weights[i] up to W.

B. Add memoization to the recursive solution to avoid recomputation.

C. Change the inner loop to iterate backwards from W down to weights[i].

D. Use a greedy approach selecting items with the highest value-to-weight ratio repeatedly.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be chosen multiple times, so dp[w] can be updated using dp[w - weights[i]] from the same iteration.

2. Step 2: Identify correct iteration order

   Iterating forwards from weights[i] to W allows reuse of updated dp values within the same iteration, enabling multiple counts of the same item.

3. Step 3: Why other options fail

   Backward iteration prevents multiple usage in one iteration (wrong for unbounded). Memoization helps but is not the direct fix. Greedy fails for 0/1 and unbounded knapsack except fractional case.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables unlimited item reuse [OK]

Hint: Unbounded knapsack requires forward iteration in dp updates [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack causes incorrect results.