// Online C++ compiler to run C++ program online
#include
#include <bits/stdc++.h>
using namespace std;
int solve(vector coins,int amount,int dp[]){
if(amount==0) return 0;
int mini=INT_MAX;
if(dp[amount]!=0){
return dp[amount];
}
for(int i=0;i<coins.size();i++){
if(amount>=coins[i]){
int subprob=solve(coins,amount-coins[i],dp);
mini=min(mini,subprob+1);
}
}
dp[amount]=mini;
return dp[amount];
}
int main() {
int n, amount;
cin >> n >> amount;
vector<int> coins(n);
for(int i=0;i<n;i++){
cin >> coins[i];
}
int dp[100]={0};
dp[0]=0;
cout << solve(coins,amount,dp);
return 0;
}
this code is not working for testcase: amount=9, coins=[3,4,5]