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 coins from your wallet. You try to use the fewest coins possible by checking all smaller amounts first, like climbing stairs one step at a time.

coins: [1, 3, 4]
amount: 6
DP array indices: 0 1 2 3 4 5 6
DP values:       0 ∞ ∞ ∞ ∞ ∞ ∞
(∞ means not yet computed)

Dry Run Walkthrough

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

Goal: Find the minimum number of coins needed to make amount 6

Step 1: Initialize DP array with 0 for amount 0 and infinity for others

DP: [0, ∞, ∞, ∞, ∞, ∞, ∞]

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

Step 2: Calculate minimum coins for amount 1 using coins

DP: [0, 1, ∞, ∞, ∞, ∞, ∞]

Why: Using coin 1, min coins for 1 is 1

Step 3: Calculate minimum coins for amount 2

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

Why: Using coin 1 twice, min coins for 2 is 2

Step 4: Calculate minimum coins for amount 3

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

Why: Using coin 3 once, min coins for 3 is 1

Step 5: Calculate minimum coins for amount 4

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

Why: Using coin 4 once, min coins for 4 is 1

Step 6: Calculate minimum coins for amount 5

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

Why: Using coin 1 + min coins for 4 (1), total 2

Step 7: Calculate minimum coins for amount 6

DP: [0, 1, 2, 1, 1, 2, 2]

Why: Using coin 3 + min coins for 3 (1), total 2

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

int minCoins(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0; // base case

    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX; // initialize with infinity
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                int sub_res = dp[i - coins[j]] + 1;
                if (sub_res < dp[i]) {
                    dp[i] = sub_res; // update min coins for amount i
                }
            }
        }
    }

    if (dp[amount] == INT_MAX) {
        return -1; // no solution
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 3, 4};
    int amount = 6;
    int n = sizeof(coins) / sizeof(coins[0]);

    int result = minCoins(coins, n, amount);
    if (result == -1) {
        printf("No solution\n");
    } else {
        printf("Minimum coins needed: %d\n", result);
    }
    return 0;
}

dp[0] = 0; // base case

Set 0 coins needed to make amount 0

dp[i] = INT_MAX; // initialize with infinity

Start with no known solution for amount i

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

Check if coin can be used and subproblem has solution

dp[i] = sub_res; // update min coins for amount i

Update dp[i] if using coin j leads to fewer coins

if (dp[amount] == INT_MAX) return -1;

Return -1 if no combination can make amount

Output

Minimum coins needed: 2

Complexity Analysis

Time: O(n * amount) because we compute minimum coins for each amount up to target, checking all coins

Space: O(amount) for the dp array storing minimum coins for each amount

vs Alternative: Compared to recursive brute force exponential time, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

amount is 0

Returns 0 immediately since no coins are needed

DSA C

dp[0] = 0; // base case

no coins can make the amount

Returns -1 indicating no solution

DSA C

if (dp[amount] == INT_MAX) return -1;

coins array empty

Returns -1 since no coins available to form amount

DSA C

if (dp[amount] == INT_MAX) return -1;

When to Use This Pattern

When asked for the fewest items to reach a total from given options, use the Coin Change Minimum Coins pattern with dynamic programming to build solutions from smaller totals.

Common Mistakes

Mistake: Not initializing dp array properly leading to incorrect minimum calculations
Fix: Initialize dp[i] with a large number (infinity) before updating with minimum values

Mistake: Not checking if subproblem dp[i - coin] is solvable before adding 1
Fix: Add condition to skip if dp[i - coin] is infinity (no solution)

Summary

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

Use when you want the smallest count of coins to form a specific amount.

Build the solution bottom-up by solving smaller amounts first and using those results to solve bigger amounts.