Minimizing Coins

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.

For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.

Example:

Input:  n = 3, m = 11, a = {1, 5, 7}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int minimizingCoins(int n, int m, vector<int> &a)
{

    vector<int> dp(m + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i - a[j] >= 0)
            {
                dp[i] = min(dp[i], dp[i - a[j]] + 1);
            }
        }
    }

    if (dp[m] < INF)
        return dp[m];
    return -1;
}

int main()
{

    int n = 3, m = 11;

    vector<int> a = {1, 5, 7};

    cout << minimizingCoins(n, m, a) << "\n";

    return 0;
}