Coin Change Minimum Coins in DSA C++ - Execution Trace

Concept Flow - Coin Change Minimum Coins

Start with amount

↓

Initialize DP array with large values

↓

Set dp[0

↓

For each coin

↓

For each amount from coin to target

↓

Update dp[amount

↓

After all coins processed

↓

Check dp[target

↓

If dp[target

We build a table dp where dp[x] is the minimum coins needed for amount x. We update dp by trying each coin for all amounts.

Execution Sample

DSA C++

int coinChange(vector<int>& coins, int amount) {
  vector<int> dp(amount+1, amount+1);
  dp[0] = 0;
  for (int coin : coins) {
    for (int x = coin; x <= amount; x++) {
      dp[x] = min(dp[x], dp[x - coin] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

This code finds the minimum number of coins needed to make the given amount using the given coin denominations.

Execution Table

Step	Operation	Amount Index	dp Array State	Update Explanation
0	Initialize dp	0 to 5	[0, 6, 6, 6, 6, 6]	dp[0] = 0, others set to amount+1 (6) as infinity
1	Process coin 1	1	[0, 1, 6, 6, 6, 6]	dp[1] = min(6, dp[0]+1) = 1
2	Process coin 1	2	[0, 1, 2, 6, 6, 6]	dp[2] = min(6, dp[1]+1) = 2
3	Process coin 1	3	[0, 1, 2, 3, 6, 6]	dp[3] = min(6, dp[2]+1) = 3
4	Process coin 1	4	[0, 1, 2, 3, 4, 6]	dp[4] = min(6, dp[3]+1) = 4
5	Process coin 1	5	[0, 1, 2, 3, 4, 5]	dp[5] = min(6, dp[4]+1) = 5
6	Process coin 2	2	[0, 1, 1, 3, 4, 5]	dp[2] = min(2, dp[0]+1) = 1
7	Process coin 2	3	[0, 1, 1, 2, 4, 5]	dp[3] = min(3, dp[1]+1) = 2
8	Process coin 2	4	[0, 1, 1, 2, 2, 5]	dp[4] = min(4, dp[2]+1) = 2
9	Process coin 2	5	[0, 1, 1, 2, 2, 3]	dp[5] = min(5, dp[3]+1) = 3
10	Process coin 5	5	[0, 1, 1, 2, 2, 1]	dp[5] = min(3, dp[0]+1) = 1
11	End	-	[0, 1, 1, 2, 2, 1]	dp[5] = 1 means minimum coins for amount 5 is 1

💡 All coins processed, dp array finalized with minimum coins for each amount

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 11 (Final)
dp	[0,6,6,6,6,6]	[0,1,2,3,4,5]	[0,1,1,2,2,3]	[0,1,1,2,2,1]
coin	N/A	1	2	5
amount index (x)	N/A	5	5	5

Key Moments - 3 Insights

Why do we initialize dp array with amount+1 (like 6) instead of zero?

We use amount+1 as a large number to represent 'infinity' because we want to find minimum coins. Zero would wrongly suggest zero coins needed for amounts other than zero. See execution_table step 0.

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

dp[0] = 0 means zero coins are needed to make amount zero. This is the base case that allows building solutions for larger amounts. See execution_table step 0.

How does dp[x] get updated when processing each coin?

For each amount x, dp[x] is updated to the minimum between current dp[x] and dp[x - coin] + 1 (using one more coin). This ensures we keep the smallest number of coins needed. See execution_table steps 1 to 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of dp[2] after processing coin 2?

A 6

B 2

C 1

D 0

💡 Hint

Check the dp Array State column at step 6 in execution_table

At which step does dp[5] first get updated to 3?

A Step 5

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the Update Explanation and dp Array State columns for dp[5] in execution_table

If we remove coin 1 from the coins list, what would be the dp[1] value after processing all coins?

A 6

B 0

C 1

D -1

💡 Hint

Without coin 1, dp[1] cannot be formed, so it remains the initial large value (amount+1), see variable_tracker dp values

Concept Snapshot

Coin Change Minimum Coins:
- Use dp array where dp[x] = min coins for amount x
- Initialize dp with amount+1 (infinity), dp[0] = 0
- For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1)
- Result is dp[amount], if > amount then no solution (-1)
- Bottom-up dynamic programming approach

Full Transcript

The Coin Change Minimum Coins problem finds the fewest coins needed to make a target amount from given coin denominations. We use a dp array where dp[x] stores the minimum coins needed for amount x. Initially, dp is set to amount+1 (a large number) except dp[0] which is zero because zero coins are needed for amount zero. We then iterate over each coin and for each amount from coin value up to target amount, we update dp[amount] to the minimum of its current value and dp[amount - coin] + 1. This means we try using the current coin and see if it reduces the number of coins needed. After processing all coins, dp[amount] holds the minimum coins needed or remains large if no solution exists. The example traces dp updates step-by-step for coins [1,2,5] and amount 5, showing how dp array changes and the final answer is 1 coin (coin 5).

Practice

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

easy

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

B. The total number of different coins available

C. The maximum amount of money you can make with given coins

D. The 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 fewest number of coins needed to make a given amount correctly describes this goal, while others describe unrelated concepts.

3. Final Answer:

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

4. Quick Check:

   Minimum coins = fewest coins needed [OK]

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

Common Mistakes:

• Confusing minimum coins with total coin types
• Thinking about maximum amount instead of minimum coins
• Mixing sum of coins with count of coins

2. Which of the following is the correct C++ syntax to declare a vector named dp of size amount+1 initialized with INT_MAX?

easy

A. vector<int> dp(amount, 0);

B. std::vector dp(amount+1, INT_MAX);

C. std::vector<int> dp(amount+1, INT_MAX);

D. vector<int> dp = new vector(amount+1, INT_MAX);

Solution

1. Step 1: Check vector declaration syntax

   Correct syntax uses std::vector<int> dp(size, initial_value); std::vector<int> dp(amount+1, INT_MAX); matches this exactly.

2. Step 2: Identify errors in other options

   vector<int> dp(amount, 0); initializes with 0 and wrong size; std::vector dp(amount+1, INT_MAX); misses template brackets; vector<int> dp = new vector(amount+1, INT_MAX); uses incorrect new syntax.

3. Final Answer:

   std::vector<int> dp(amount+1, INT_MAX); -> Option C

4. Quick Check:

   Correct vector declaration = std::vector<int> dp(amount+1, INT_MAX); [OK]

Hint: Use std::vector<Type> name(size, value) for initialization [OK]

Common Mistakes:

• Omitting template brackets <>
• Using wrong initialization syntax
• Confusing size and initial value parameters

3. What is the output of the following C++ code snippet?

int coins[] = {1, 2, 5};
int amount = 11;
std::vector<int> dp(amount+1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
  for (int c : coins) {
    if (i - c >= 0 && dp[i - c] != INT_MAX) {
      dp[i] = std::min(dp[i], dp[i - c] + 1);
    }
  }
}
std::cout << dp[amount] << std::endl;

medium

A. 11

B. 3

C. 5

D. INT_MAX

Solution

1. Step 1: Understand the DP approach

   The code finds minimum coins to make amount 11 using coins {1,2,5} by building dp array.

2. Step 2: Calculate minimum coins for 11

   11 = 5 + 5 + 1 uses 3 coins, which is minimum. dp[11] = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Minimum coins for 11 = 3 [OK]

Hint: Try largest coins first to minimize count [OK]

Common Mistakes:

• Assuming dp[amount] remains INT_MAX
• Counting total coin value instead of count
• Ignoring dp initialization and updates

4. Identify the error in this C++ code snippet for Coin Change Minimum Coins:

int coins[] = {1, 3, 4};
int amount = 6;
std::vector<int> dp(amount+1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
  for (int c : coins) {
    if (i - c >= 0) {
      dp[i] = std::min(dp[i], dp[i - c] + 1);
    }
  }
}
std::cout << dp[amount] << std::endl;

medium

A. dp[0] should be initialized to INT_MAX

B. Wrong initialization of dp vector size

C. Incorrect coin denominations array syntax

D. Missing check if dp[i - c] is INT_MAX before adding 1

Solution

1. Step 1: Analyze dp update condition

   The code updates dp[i] without checking if dp[i - c] is INT_MAX, which can cause overflow.

2. Step 2: Identify missing condition

   Must check dp[i - c] != INT_MAX before adding 1 to avoid invalid calculations.

3. Final Answer:

   Missing check if dp[i - c] is INT_MAX before adding 1 -> Option D

4. Quick Check:

   Check dp[i - c] != INT_MAX before update [OK]

Hint: Always check dp[i-c] != INT_MAX before adding 1 [OK]

Common Mistakes:

• Skipping dp[i-c] validity check
• Incorrect dp vector size
• Wrong initialization of dp[0]

5. Given coin denominations {2, 5, 10} and amount 7, what is the minimum number of coins needed? If it is not possible, return -1.

hard

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins are 2, 5, 10. 10 > 7 so ignore. Try 5 + 2 = 7 (2 coins). But 5 + 2 is valid, so minimum coins = 2.

2. Step 2: Verify if 5 + 2 is allowed

   Since 5 and 2 are in denominations, 7 can be made with 2 coins.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   7 = 5 + 2 uses 2 coins [OK]

Hint: Try combinations starting from largest coin [OK]

Common Mistakes:

• Assuming no solution because 7 is odd
• Ignoring valid combinations with smaller coins
• Returning -1 incorrectly