I was trying to solve exactly the same question online

Expected

Input: coins = [2], amount = 3

Output: -1

Input

[2]

3

Output

0

Expected

-1

class Solution {

public:

long long int coinChange(vector& coins, long long int amount) {

```
long long int dp[100000]={0};
if (amount == 0)
{
return 0;
}
if (dp[amount] != 0)
{
return dp[amount];
}
long long int ans = INT_MAX;
for (int i = 0; i < coins.size(); i++)
{
if (amount - coins[i] >= 0)
{
long long int subProb = coinChange(coins, amount - coins[i]);
ans = min(ans, subProb + 1);
}
}
dp[amount] = ans;
return dp[amount]==INT_MAX?-1:dp[amount];
}
```

};