Why coin change is not working


#1

Runtime Error. Your submission stopped because of a runtime error. ex: division by zero, array index out of bounds, uncaught exception You can try testing your code with custom input and try putting debug statements in your code.

terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc

Code:
int coinChange(vector& coins, int amount) {

    int n=coins.size();
    vector<vector<int>> dp(n+1,vector<int>(amount+1));
    
    for(int i=0;i<=n;i++)dp[i][0]=0;
    for(int j=1;j<=amount;j++)dp[0][j]=INT_MAX-1;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=amount;j++){
            if(coins[i-1]<=j)dp[i][j]=min(1+dp[i][j-coins[i-1]],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    
 
    if(dp[n][amount]==INT_MAX-1)return -1;
    return dp[n][amount];
    
}

int Solution::fibsum(int A) {

vector<int> fab={1,1};

while(fab.back()<2*A){
    int size=fab.size();
    fab.push_back(fab[size-1]+fab[size-2]);
}
return coinChange(fab,A);

}


#2

Its because of the constraints .Lets say for A=1e9 and hence the runtime error.