Coin Change Minimum Coins in DSA C - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount = 0

↓

Initialize dp array with large values

↓

Set dp[0

↓

For each amount from 1 to target

↓

For each coin

↓

If coin <= amount

↓

Update dp[amount

↓

Repeat until dp[target

↓

If dp[target

We build a table dp where dp[i] stores the minimum coins needed for amount i. We fill dp from 0 to target by checking all coins.

Execution Sample

DSA C

int coins[] = {1, 3, 4};
int target = 6;
int dp[7];
// dp[0] = 0, others large
// Fill dp from 1 to 6
// dp[i] = min(dp[i], dp[i-coin]+1)

This code finds the minimum coins needed to make amount 6 using coins 1, 3, and 4.

Execution Table

Step	Operation	Amount i	Coin Used	dp Array State	Explanation
1	Initialize dp	-	-	[0, 999, 999, 999, 999, 999, 999]	dp[0] = 0, others set to large number (999)
2	Check amount	1	1	[0, 1, 999, 999, 999, 999, 999]	dp[1] = min(999, dp[0]+1)=1
3	Check amount	2	1	[0, 1, 2, 999, 999, 999, 999]	dp[2] = min(999, dp[1]+1)=2
4	Check amount	3	1	[0, 1, 2, 3, 999, 999, 999]	dp[3] = min(999, dp[2]+1)=3
5	Check amount	3	3	[0, 1, 2, 1, 999, 999, 999]	dp[3] = min(3, dp[0]+1)=1 (using coin 3)
6	Check amount	4	1	[0, 1, 2, 1, 2, 999, 999]	dp[4] = min(999, dp[3]+1)=2
7	Check amount	4	3	[0, 1, 2, 1, 2, 999, 999]	dp[4] = min(2, dp[1]+1)=2 (no change)
8	Check amount	4	4	[0, 1, 2, 1, 1, 999, 999]	dp[4] = min(2, dp[0]+1)=1 (using coin 4)
9	Check amount	5	1	[0, 1, 2, 1, 1, 2, 999]	dp[5] = min(999, dp[4]+1)=2
10	Check amount	5	3	[0, 1, 2, 1, 1, 2, 999]	dp[5] = min(2, dp[2]+1)=2 (no change)
11	Check amount	5	4	[0, 1, 2, 1, 1, 2, 999]	dp[5] = min(2, dp[1]+1)=2 (no change)
12	Check amount	6	1	[0, 1, 2, 1, 1, 2, 3]	dp[6] = min(999, dp[5]+1)=3
13	Check amount	6	3	[0, 1, 2, 1, 1, 2, 2]	dp[6] = min(3, dp[3]+1)=2 (using coin 3)
14	Check amount	6	4	[0, 1, 2, 1, 1, 2, 2]	dp[6] = min(2, dp[2]+1)=2 (no change)
15	Result	6	-	[0, 1, 2, 1, 1, 2, 2]	Minimum coins for 6 is 2
16	End	-	-	-	dp[6] found, algorithm stops

💡 dp[6] computed as 2, meaning minimum 2 coins needed for amount 6

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 13	Final
dp[0]	0	0	0	0	0	0
dp[1]	999	1	1	1	1	1
dp[2]	999	999	2	2	2	2
dp[3]	999	999	1	1	1	1
dp[4]	999	999	999	1	1	1
dp[5]	999	999	999	999	2	2
dp[6]	999	999	999	999	2	2

Key Moments - 3 Insights

Why do we initialize dp array with a large number like 999?

We use a large number to represent 'infinity' or no solution yet. This helps us find the minimum by comparing and updating dp values. See Step 1 in execution_table.

Why do we set dp[0] = 0 at the start?

Because zero coins are needed to make amount zero. This is the base case that allows building solutions for larger amounts. See Step 1 in execution_table.

Why do we update dp[i] with dp[i - coin] + 1?

Because if we can make amount (i - coin) with dp[i - coin] coins, then adding one coin of value 'coin' makes amount i with one more coin. We take the minimum over all coins. See Steps 5, 8, and 13.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the value of dp[3] after using coin 3?

A 1

B 3

C 0

D 999

💡 Hint

Check the dp Array State column at Step 5 in execution_table.

At which step does dp[4] get updated to 1 for the first time?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the dp Array State and Coin Used columns for amount 4 in execution_table.

If we remove coin 3 from the coin list, what would be the minimum coins for amount 6?

A 2

B 3

C 4

D Impossible

💡 Hint

Without coin 3, dp[6] would rely on coins 1 and 4 only; check how dp[6] was updated in Steps 13 and 14.

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array where dp[i] = min coins for amount i
- Initialize dp[0] = 0, others large
- For each amount i, for each coin:
  if coin <= i, dp[i] = min(dp[i], dp[i-coin]+1)
- dp[target] gives minimum coins or no solution if large

Full Transcript

This visualization shows how to find the minimum number of coins needed to make a target amount using given coin denominations. We create a dp array where each index represents an amount from 0 up to the target. We start by setting dp[0] to 0 because no coins are needed for amount zero, and all other dp values to a large number representing no solution yet. Then, for each amount from 1 to the target, we check each coin. If the coin value is less than or equal to the current amount, we update dp[amount] to the minimum of its current value and dp[amount - coin] plus one coin. This process continues until we fill dp[target]. The final dp[target] value is the minimum coins needed or indicates no solution if it remains large. The execution table traces each update step by step, showing how dp array changes and which coin is used. Key moments clarify why initialization is done with large numbers, why dp[0] is zero, and why dp updates use dp[i - coin] + 1. The quiz tests understanding of dp updates and the effect of removing a coin.