Coin Change :Dynamic Programming

Question

The code I have written solves the basic coin change problem using dynamic programming and gives the minimum number of coins required to make the change. But I want to store the count of each coin playing part in the minimum number.

What I am trying to do is initializing an array count[] and just like hashing it increments the number of coin[j] whenever min is found, i.e count[coin[j]]++ . But this is not working the way I wanted because it adds the coin every time it finds min corresponding to coin[j]. Hence the number is not the final count of coin in the final answer.

Here is the code:

void makeChange(int coin[], int n, int value)
{
    int i, j;
    int min_coin[MAX];
    int min;

    int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
            min = 999;
            for (j = 0; j<n; j++)
            {
                    if (coin[j] <= i)
                    {
                            if (min > min_coin[i-coin[j]]+1)
                            {
                                    min = min_coin[i-coin[j]]+1;
                                    count[coin[j]]++;
                            }
                    }
            }
            min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);

}

Answer 1

You have to keep an extra, two-dinemsional array to store the coin count for each value and each coin denomination.

When you assign a new minimum in your inner loop, copy all coin counts from i - coin[j] to i and then increment min_count[i][j]. The number of coins needed is then in coin_count[value].