Coin Change Minimum Coins in DSA C++

Mental Model

Find the smallest number of coins needed to make a target amount using given coin values. We build up solutions from smaller amounts to the target.

Analogy: Imagine you want to pay a certain amount using the fewest coins from your wallet. You try to pay smaller amounts first and remember the best way to pay them, then use that knowledge to pay bigger amounts.

coins: [1, 3, 4]
amount: 6

DP array (index = amount):
[0] [1] [2] [3] [4] [5] [6]
 ↑   ↑   ↑   ↑   ↑   ↑   ↑
 0   ?   ?   ?   ?   ?   ?

Dry Run Walkthrough

Input: coins: [1, 3, 4], amount: 6

Goal: Find minimum coins needed to make amount 6

Step 1: Initialize dp array with dp[0] = 0 and others as infinity (unreachable)

dp: [0, ∞, ∞, ∞, ∞, ∞, ∞]

Why: Base case: zero coins needed to make amount 0

Step 2: Calculate dp[1]: check coins 1,3,4; only coin 1 fits, dp[1] = dp[0] + 1 = 1

dp: [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: Amount 1 can be made with one coin of 1

Step 3: Calculate dp[2]: check coins 1,3,4; only coin 1 fits, dp[2] = dp[1] + 1 = 2

dp: [0, 1, 2, ∞, ∞, ∞, ∞]

Why: Amount 2 can be made with two coins of 1

Step 4: Calculate dp[3]: check coins 1,3,4; coin 3 fits, dp[3] = min(dp[2]+1, dp[0]+1) = min(3,1) = 1

dp: [0, 1, 2, 1, ∞, ∞, ∞]

Why: Amount 3 can be made with one coin of 3

Step 5: Calculate dp[4]: check coins 1,3,4; coin 4 fits, dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = min(2,2,1) = 1

dp: [0, 1, 2, 1, 1, ∞, ∞]

Why: Amount 4 can be made with one coin of 4

Step 6: Calculate dp[5]: check coins 1,3,4; dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(2,3,2) = 2

dp: [0, 1, 2, 1, 1, 2, ∞]

Why: Amount 5 can be made with two coins (4+1 or 3+1+1)

Step 7: Calculate dp[6]: check coins 1,3,4; dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3,2,3) = 2

dp: [0, 1, 2, 1, 1, 2, 2]

Why: Amount 6 can be made with two coins (3+3 or 4+1+1)

Result:

dp: [0, 1, 2, 1, 1, 2, 2]
Minimum coins needed: 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int minCoins(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0; // base case: 0 coins to make amount 0

    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1); // update dp[i] with fewer coins if possible
            }
        }
    }

    return dp[amount] == INT_MAX ? -1 : dp[amount]; // -1 if no solution
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    int result = minCoins(coins, amount);
    cout << result << endl;
    return 0;
}

dp[0] = 0; // base case: 0 coins to make amount 0

initialize base case for dp array

for (int i = 1; i <= amount; ++i) {

iterate over all amounts from 1 to target

for (int coin : coins) {

check each coin for current amount

if (coin <= i && dp[i - coin] != INT_MAX) {

only consider coin if it fits and previous amount is reachable

dp[i] = min(dp[i], dp[i - coin] + 1); // update dp[i] with fewer coins if possible

update dp[i] to minimum coins needed

return dp[amount] == INT_MAX ? -1 : dp[amount]; // -1 if no solution

return result or -1 if no combination found

Output

2

Complexity Analysis

Time: O(n * amount) because we compute dp for each amount up to target and check all n coins each time

Space: O(amount) because we store minimum coins needed for all amounts up to target

vs Alternative: Compared to recursive brute force exponential approach, this dynamic programming solution is much faster and avoids repeated work

Edge Cases

amount = 0

returns 0 because no coins are needed

DSA C++

dp[0] = 0; // base case: 0 coins to make amount 0

coins array empty

returns -1 because no coins available to make any amount

DSA C++

return dp[amount] == INT_MAX ? -1 : dp[amount]; // -1 if no solution

amount cannot be formed by given coins

returns -1 indicating no solution

DSA C++

return dp[amount] == INT_MAX ? -1 : dp[amount]; // -1 if no solution

When to Use This Pattern

When asked to find the minimum number of items to reach a target sum from given options, use dynamic programming with a bottom-up approach to build solutions from smaller sums.

Common Mistakes

Mistake: Not initializing dp array with a large value, causing incorrect minimum calculations
Fix: Initialize dp array with INT_MAX or a large number to represent unreachable amounts

Mistake: Not checking if dp[i - coin] is reachable before using it
Fix: Add condition to skip dp[i - coin] if it is INT_MAX to avoid invalid calculations

Summary

Finds the minimum number of coins needed to make a target amount using given coin denominations.

Use when you need the fewest items to sum up to a value from a set of options.

Build solutions from smaller amounts up to the target, remembering the best way to make each amount.

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