dynamic programming, coin change, memory leak?

Question

I writing program to change coin. When i write printf in loops to print i or j program give good results, when I delete it, program stops. I think it's problem with memory but I'm writing on Windows in QT and i have no access to valgrind.

Anyone can check this? First give numbers of denomination, second - denominations, last is amount.

E.g:

3
1 3 5
8

result should be 2.

1
5
3

result sholud be NO.

#include <stdio.h>
#include <stdlib.h>

#define INF 2147483647 //nieskonczonosc


void nominal(int nominaly, int T[], int k)
{
    int i;
    for (i=1; i<=nominaly; i++ )          
       {
         int n=0;
         scanf("%d", &n);           
         int j;                     
         for ( j=0;j<=k-n;++j) {  
           if (T[j] < INF)                       
             if (T[j]+1 < T[j+n])   
               T[j+n] = T[j]+1;

       }
    }

    int kwota=0;
    scanf("%d", &kwota);
    if(T[kwota]==INF){
        printf("NO");
    }else
    printf("%d", T[kwota]);

}

int main() {

    int n=0;

    scanf("%d", &n);

    int k=10000;
    int *T;
    T = (int*)malloc(k * sizeof(int));
    T[0]=0;
    int i;
    for (i=1;i<=k;++i)
        {                   
         T[i]=INF;
         }
    nominal(n, T, k);

    free(T);
    return 0;

}

Answer 1

Assuming the input is well-formed, the only problem I can spot in your code is in these lines:

if (T[j]+1 < T[j+n])   
    T[j+n] = T[j]+1;

When j reaches the value k-n, T[j+n] is an out-of-bounds access, because you get k-n+n, so you are accessing T[k], and the last valid position is T[k-1]. This invokes undefined behavior in your program - anything (including working as expected) can happen.

You might want to rewrite that for loop to something like:

for (j=0; j < k-n;++j) { ... }

There are no memory leaks in your code.