1 year ago
#342761
Pedro Barbeira
Heap corruption on dynamic programming problem
I'm getting an heap corruption error and I can't figure out where it is.
The problem is a coin change problem using dynamic programming. C is the array with the coin values, n is the size of the array, T is the target change, usedCoins is an array where the number of used coins should be mapped (i.e if C[1] = 2 and 3 2-coins are used, usedCoins[2] = 2 with all other indexes to 0.
Here's the code:
bool changeMakingUnlimitedDP(unsigned int C[], unsigned int n, unsigned int T, unsigned int usedCoins[]) {
static auto minCoins = new unsigned int[T+1]{UINT_MAX};
minCoins[0] = 0;
static auto lastCoin = new unsigned int[T+1]{0};
for(int i = 0; i < n; i++)
usedCoins[i] = 0;
for(int i = 0; i < n; i++){
for(int j = 1; j <= T; j++){
if(j >= C[i]){
minCoins[j-C[i]] == 0? minCoins[j] = 1 : minCoins[j] = std::min(1 + minCoins[j - C[i]], minCoins[j-C[i]]);
lastCoin[j] = i;
}
}
}
while(T > 0){
unsigned int last = lastCoin[T];
if(last == UINT_MAX || last < 0) return false;
usedCoins[last]++;
T -= C[last];
}
free(minCoins);
free(lastCoin);
return true;
}
When running on debug mode it goes through.
c++
heap-corruption
0 Answers
Your Answer