#include<bits/stdc++.h>
using namespace std;
int Min_Coins(int n,int coins[],int T,int dp[])
{
if(n==0)
{
return 0;
}
if(dp[n]!=0)
{
return dp[n];
}
int ans=INT_MAX;
for(int i=0;i<T;i++)
{
if(n-coins[i]>=0)
{
int subproblem=Min_Coins(n-coins[i],coins,T,dp);
ans=min(ans,subproblem+1);
}
}
return dp[n]=ans;
}
int Min_Coins_BU(int n,int coins[],int T)
{
int dp[100]={0};
for(int i=1;i<=n;i++)
{
dp[i]=INT_MAX;
for(int j=0;j<T;j++)
{
if(n-coins[j]>=0)
{
int subproblem=dp[n-coins[j]];
dp[i]=min(dp[i],subproblem+1);
}
}
}
return dp[n];
}
int main()
{
int n=15;
int coins[]={1,7,10};
int dp[100]={0};
int T=sizeof(coins)/sizeof(int);
cout<<Min_Coins_BU(n,coins,T);
}