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.
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.
Step 1/21
·Active fill★Answer cell
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/5)
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
Step 1: Understand problem constraints
The problem requires minimizing the difference between sums of two subsets, which is a classic partition problem variant.
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.
Hint: Minimal difference requires subset-sum DP, not greedy [OK]
Common Mistakes:
Assuming greedy or sorting suffices for minimal difference
2. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?
def count_ways_space_opt(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for w in range(coin, amount + 1):
dp[w] += dp[w - coin]
return dp[amount]
coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))
easy
A. 4
B. 7
C. 5
D. 6
Solution
Step 1: Trace dp array updates for each coin
Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].
Step 2: Confirm dp[5] value
dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].
Final Answer:
Option D -> Option D
Quick Check:
Manual dp tracing matches output 6 [OK]
Hint: DP accumulates counts incrementally per coin [OK]
Common Mistakes:
Off-by-one in dp indexing
Miscounting after last coin iteration
Confusing permutations with combinations
3. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?
medium
A. Line 5: inner loop iterating backwards over amounts
B. Line 4: outer loop over coins
C. Line 2: dp initialization
D. Line 6: updating dp[w] with dp[w - coin]
Solution
Step 1: Understand iteration order effect
Iterating amounts backwards causes dp to count permutations, not combinations.
Step 2: Identify bug line
Line 5 iterates w from amount down to coin, which breaks combination counting logic.
Final Answer:
Option A -> Option A
Quick Check:
Forward iteration over amounts is required to count combinations correctly [OK]
Hint: Check direction of inner loop iteration [OK]
Common Mistakes:
Using backward iteration in 1D dp
Misplacing dp[0] initialization
4. What is the time complexity of the optimal job scheduling algorithm that sorts jobs by end time and uses binary search with a DP array of size n?
medium
A. O(n log W) where W is the maximum end time
B. O(n^2) due to nested loops over all jobs
C. O(n) because each job is processed once
D. O(n log n) due to sorting and binary searches for each job
Solution
Step 1: Identify sorting cost
Sorting n jobs by end time costs O(n log n).
Step 2: Analyze DP loop with binary search
For each job, binary search among ends array costs O(log n), repeated n times -> O(n log n).
Final Answer:
Option D -> Option D
Quick Check:
Sorting + n binary searches dominate; no nested O(n^2) loops [OK]
5. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?
medium
A. Line 3: Missing base case assignment dp[0] = 0
B. Line 2: dp initialization with infinity
C. Line 5: Outer loop from 1 to n
D. Line 7: Inner loop condition j*j <= i
Solution
Step 1: Identify base case importance
dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
Step 2: Analyze impact of missing dp[0] = 0
Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
Final Answer:
Option A -> Option A
Quick Check:
Missing dp[0] base case breaks DP initialization [OK]
Hint: dp[0] must be zero to start DP correctly [OK]
Common Mistakes:
Forgetting dp[0] initialization
Misplacing loop boundaries
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.