Find the minimum number of coins

Find the minimum number of coins required to make n cents.

You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

For example, given n = 16, return 3 since we can make it with a 10¢, a 5¢, and a 1¢.

Example:

Input:  coins = {1,5,10,25}, value = 16
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
int minCoins(vector<int> &coinList, int value)
{
    int n = coinList.size();
    int coins[value + 1];
    if (value == 0)
        return 0;
    coins[0] = 0;
    for (int i = 1; i <= value; i++)
        coins[i] = INT_MAX;
    for (int i = 1; i <= value; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (coinList[j] <= i)
            {
                int tempCoins = coins[i - coinList[j]];
                if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
                    coins[i] = tempCoins + 1;
            }
        }
    }
    return coins[value];
}
int main()
{
    vector<int> coinList = {1, 5, 10, 25};
    int value = 16;
    cout << minCoins(coinList, value);
    return 0;
}