coins.cpp

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


const int INF = 1e9;
vector<int> dp;

int solve(int m, vector<int> &coins){
    if(m < 0) return INF;
    if(m == 0) return 0;
    if(dp[m] != -1)
        return dp[m];
    int res = INF;
    for(int i = 0; i < coins.size(); i++){
        res = min(res, 1 + solve(m - coins[i], coins));
    }
    return dp[m] = res;
}

int minimumNumberCoins(int m, vector<int> &coins){
    dp.assign(m+1, -1);
    int res = solve(m, coins);
    return res == INF ? -1 : res;
}

int main(){
    vector<int> v = {5, 10};
    int m = 14;
    int res = minimumNumberCoins(m, v);
    cout << res << '\n';
    return 0;
}