Giving wrong output for 1 coin

#1

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];
 
    
}

};

#2

hi @anandsingh3210
Kindly save ur code on coding Blocks ide and send link…

#3

i was solving this problem on leetcode. https://leetcode.com/problems/coin-change/submissions/

#4 
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[amount+1];
        dp[0] = 0;
        
        for(int i=1;i<=amount;i++){
            dp[i] = INT_MAX;
            for(int j=0;j<coins.size();j++){
                if(i-coins[j] >=0 && dp[i-coins[j]] != INT_MAX){
                    dp[i] = min(dp[i], dp[i-coins[j]]+1);
                }
            }
        }
        if(dp[amount] == INT_MAX){
            return -1;
        }
        return dp[amount];
    }
};

Refer this

#5

i did not understand this solution.

#6

can you change anything in my code

#7 
class Solution {
public:
    int solve(vector<int>& coins, int amt, int dp[]) {
        // ----------------- Base case  -----------------
		if(amt == 0) return 0;
        
        // ----------------- Checking if value exists in DP (or Memoization Check)  -----------------
		if(dp[amt]) return dp[amt];
        
        // ----------------- Recurrence relation  -----------------
		int minv = INT_MAX; 
        
		//Iterating over coins array and performing recurrence relation for every coin
		for(int i=0; i< coins.size(); i++){
            if(coins[i]<=amt){
                int temp = solve(coins, amt - coins[i], dp); 
                if(temp + 1L < minv) minv = temp+1;   //L is a suffix (long int) because INT_MAX +1 isn't INT!
				                                      //So, it will give INT over-boundary error, if we don't typecast it!
            }
        }
        
        return dp[amt] = minv;
    }
    
    int coinChange(vector<int>& coins, int amount) {
        int dp[10002]= {0};
        int res = solve(coins, amount, dp);
        return res==INT_MAX ? -1 : res; 
    }
};
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.