I was solving a question on Leetcode(322. Coin Change) and I wrote my solution which is working on VScode. the code is:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1,999));
for(int i=0;i<n+1;i++)
dp[i][0] = 0;
for(int i=0;i<amount+1;i++){
dp[0][i] = 999;
}
for(int i=1;i<n+1;i++){
for(int j=1;j<amount+1;j++){
if(coins[i-1]<=amount)
dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );
else
dp[i][j] = dp[i-1][j];
}
}
if(dp[n][amount]>=999) return -1;
return dp[n][amount];
}
upon running for testcase coins = [1,2,5], amount = 11, it I'm getting the following error
Line 1117: Char 34: runtime error: addition of unsigned offset to 0x504000000110 overflowed to 0x50400000010c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/stl_vector.h:1126:34
In the line:
dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );
When indexing into dp
, j-coins[i-1]
can be less than 0 because coins[i-1]
can be grater than j
.
This could cause the runtime error you are seeing. I would suggest running the code under a debugger and stepping through the loop to see what the values of the indexes are at different points in time.