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.

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?

easy

A. The smallest number of coins needed to make a given amount

B. The total number of different coins available

C. The largest coin value in the set

D. The total sum of all coin values

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of coins needed to make a specific amount using given coin denominations.

2. Step 2: Identify the correct description

   The smallest number of coins needed to make a given amount correctly describes this goal, while others describe unrelated concepts.

3. Final Answer:

   The smallest number of coins needed to make a given amount -> Option A

4. Quick Check:

   Minimum coins = smallest count needed [OK]

Hint: Focus on 'minimum coins' needed to form the amount [OK]

Common Mistakes:

• Confusing total coin count with minimum coins
• Thinking about coin values instead of counts
• Mixing up largest coin with minimum coins

2. Which of the following is the correct way to initialize the DP array for the Coin Change Minimum Coins problem in C?

easy

A. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = 0;

B. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = -1;

C. int dp[amount+1] = {0};

D. int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX;

Solution

1. Step 1: Understand DP initialization

   We initialize dp array with a large number (like INT_MAX) to represent impossible states initially.

2. Step 2: Identify correct initialization

   int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX; correctly sets all dp values to INT_MAX, except dp[0] which is usually set to 0 later.

3. Final Answer:

   int dp[amount+1]; for(int i=0; i<=amount; i++) dp[i] = INT_MAX; -> Option D

4. Quick Check:

   Initialize dp with max values for minimum search [OK]

Hint: Use INT_MAX to mark unreachable amounts initially [OK]

Common Mistakes:

• Initializing dp with zeros causes wrong minimum calculations
• Using -1 without handling leads to errors
• Not setting dp[0] = 0 explicitly

3. What is the output of the following code snippet for coins = {1, 3, 4} and amount = 6?

int coins[] = {1, 3, 4};
int amount = 6;
int dp[7];
for(int i=0; i<=amount; i++) dp[i] = amount+1;
dp[0] = 0;
for(int i=1; i<=amount; i++) {
  for(int j=0; j<3; j++) {
    if(coins[j] <= i) {
      dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
    }
  }
}
printf("%d\n", dp[amount]);

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace dp array updates for amount 6

   Calculate minimum coins for each amount: - dp[0]=0 - dp[1]=1 (1 coin) - dp[2]=2 (1+1) - dp[3]=1 (3 coin) - dp[4]=1 (4 coin) - dp[5]=2 (4+1) - dp[6]=2 (3+3)

2. Step 2: Final dp[6] value

   dp[6] = 2, minimum coins needed to make 6.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array from 0 to amount stepwise [OK]

Common Mistakes:

• Forgetting to update dp[i] with minimum value
• Incorrectly handling coin indices
• Assuming dp[i] equals i always

4. Identify the bug in this code snippet for Coin Change Minimum Coins:

int coins[] = {1, 2, 5};
int amount = 11;
int dp[12];
for(int i=0; i<=amount; i++) dp[i] = 0;
dp[0] = 0;
for(int i=1; i<=amount; i++) {
  for(int j=0; j<3; j++) {
    if(coins[j] <= i) {
      dp[i] = dp[i - coins[j]] + 1;
    }
  }
}
printf("%d\n", dp[amount]);

medium

A. dp array is not initialized with large values

B. dp[0] should be set to 1

C. The inner loop should run from j=1 to 3

D. The condition coins[j] <= i is incorrect

Solution

1. Step 1: Check dp initialization

   dp array is initialized with zeros, which incorrectly suggests zero coins needed for all amounts.

2. Step 2: Correct initialization needed

   dp should be initialized with a large number (like INT_MAX) to represent unreachable states, then updated with minimum coins.

3. Final Answer:

   dp array is not initialized with large values -> Option A

4. Quick Check:

   Initialize dp with max values to find minimum [OK]

Hint: Initialize dp with large values, not zeros [OK]

Common Mistakes:

• Setting dp to zero causes wrong minimum calculations
• Not updating dp[i] with minimum of previous values
• Incorrect loop ranges

5. Given coins = {2, 5, 10} and amount = 7, what is the minimum number of coins needed? If it is not possible, return -1. Use the Coin Change Minimum Coins logic.

hard

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins are 2, 5, 10. Possible sums: - 2+5=7 (2 coins) - 5+2=7 (2 coins) - 10 is too large So minimum coins = 2.

2. Step 2: Confirm no smaller combination

   Since 1-coin denominations are not available, 2 coins is minimum.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   7 = 2 + 5, minimum coins = 2 [OK]

Hint: Try all coin combos to find minimum or detect impossibility [OK]

Common Mistakes:

• Assuming 7 cannot be formed without 1-coin denomination
• Returning -1 incorrectly
• Ignoring order of coins