coin chnage 1

 

coin chnage 1

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl "\n"

ll arr[10005];

ll dp[10005];

ll coin(ll am,ll n)

{

    if(am==0)return 0;

    if(dp[am]!=-1)return dp[am];

    ll ans;

    ans=INT_MAX;

    for(ll i=0;i<n;i++)

    {

        if((am-arr[i])>=0)

        ans=min(ans,coin(am-arr[i],n)+1);

    }

    return dp[am]=ans;

}

int main()

{

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   memset(dp,-1,sizeof(dp));

   ll n,amo;

   for(ll i=0;i<n;i++)cin>>arr[i];

   ll r;

   r=coin(amo,n);

   if(r==INT_MAX)cout<<-1<<endl;

   else cout<<r<<endl;

    return 0;

}