coin_change_dp.cpp

#include <bits/stdc++.h>
using namespace std;
//bottom up approach
int coinChangeMin(vector<int> &coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int coin : coins) {
        for (int i = coin; i <= amount; ++i) {
            dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] == INF ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 11;
    cout << coinChangeMin(coins, amount) << "\n";  // Output: 3 (5+5+1)
}

//top-down approach
unordered_map<int,int> mp;

int min_coins(int tot)
{
    if(tot==0)
        return 0;
    if(mp.find(tot)!=mp.end())
        return mp[tot];

    int mncoin = INT_MAX;

    for(auto i:coins)
    {
        if(i<=tot)
        {
            int sub = min_coins(tot-i);
            mncoin = min(mncoin,sub+1);
        }
    }

    mp[tot] = mncoin;
    return mncoin;
}

// Driver Code
int main()
{
    Faster;
    ll tc = 1, test = 1;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        int ans = min_coins(n);

        cout << ans << nl;
    }
}