#include
#include
#include //forfor INT_MAX
#include //für min
using namespace std;
vector coins; //The different types of coins
vector memo; //For DP/Memorization
//Returns the smallest number of coins that are necessary to reach amount.
//If no possible, it returns -1
int numCoins(int amount)
{
if(amount == 0)
return 0;
else if(amount < 0)
return -1;
//If the value as already been calculated, simply return it
if(memo[amount] != -2)
return memo[amount];
int minimum = INT_MAX; //A very big value
//Try out all coinss
for(int coin : coins)
{
int num = numCoins(amount - coin); //Try out the coin: Let test recursively how many coins are necessary for the remaining amount.
if(num != -1) //If it is still possible to take this coin, look if it is better that what has already been tried out.
minimum = min(minimum, num);
}
if(minimum == INT_MAX) //If no single coin fitted, save and return -1
return memo[amount] = -1;
else
return memo[amount] = minimum + 1; //Otherwise take the smallest coin (+1) and the number of coins that are necessary for
//the remaining amount. Save and return it.
}
int main()
{
//Number of types of coins
int n;
cin >> n;
coins = vector(n);
//read in the types of coins
for(int i = 0; i < n; i++)
{
int coin;
cin >> coin;
coins[i] = coin;
}
//read in the amount
int amount;
cin >> amount;
//Initialize the DP-vector with -2 (which means that this value has not been calculated yet)
memo = vector(amount+1, -2);
//calculate the smallest number of coins that are necessary to reach the amount
cout << numCoins(amount) << endl;
}