1 year ago

#342761

test-img

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

Accepted video resources