Coin Change (Min Coins)

Concept

Given coin denominations and a target amount, find the minimum number of coins needed. Top-down memoization tries using each coin denomination, recursing on the remaining amount. dp[amount] stores the minimum coins for that amount.

When to Use

• ▸Minimum number of coins/bills to make a target amount
• ▸Minimum steps problems where you can take different step sizes
• ▸Any problem asking 'minimum number of X to reach Y' with fixed options

Intuition

For each amount, try every coin. If you use coin c, you need 1 + (min coins for amount-c). Try all coins and take the minimum. Base case: amount 0 needs 0 coins, negative amount is impossible. Memoize to avoid recomputation. It's like making change at a store — try each coin type and see which combination uses the fewest coins total.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9+7;
vector<int> dp;

int coinChange(vector<int>& coins, int amount) {
    if(amount == 0) return 0;
    if(amount < 0) return inf;

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

    int best = inf;
    for(int c : coins){
        best = min(coinChange(coins, amount-c), best);
    }

    return dp[amount] = best+1;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, amount;
    cin >> n;

    vector<int> coins(n);
    for(int i = 0; i < n; i++) cin >> coins[i];
    cin >> amount;

    dp.assign(amount+1, -1);
    int ans = coinChange(coins, amount);
    if(ans >= inf) return printf("%d", -1);
    return printf("%d", ans);
}

// Sample Input:
// 3
// 1 3 4
// 6
//
// Sample Output:
// 2