Coding Interview Questions: No. 26 - Minimal Number of Coins for Change

Coding Interview Questions: No. 26 - Minimal Number of Coins for Change
Problem: Please implement a function which gets the minimal number of coins, whose value is v₁, v₂, …, v_n, to make change for an amount of money with value t. Any coin with value v_i may duplicate for any times to make change.

For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.

Firstly let us define a function f(t) which is the minimal number of coins to make change for total value t. If there are n different coins, we have n choices to make change for value t:

Even though we have a 2-D matrix to show the iterative process, it only requires a 1-D array for coding, because it is only necessary to store the minimal number of coins to make change for each total value. 

int GetMinCount(int total, int* coins, int length)

{

    int* counts = new int[total + 1];

    counts[0] = 0;

   

    const int MAX = 0x7FFFFFFF;

    for(int i = 1; i <= total; ++ i)

    {

        int count = MAX;

        for(int j = 0; j < length; ++ j)

        {

            if(i - coins[j] >= 0 && count > counts[i - coins[j]])

                count = counts[i - coins[j]];

        }

        if(count < MAX)

            counts[i] = count + 1;

        else

            counts[i] = MAX;

    }

    int minCount = counts[total];

    delete[] counts;

    return minCount;

}

http://massivealgorithms.blogspot.com/2014/07/making-change.html
http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html
Read full article from Coding Interview Questions: No. 26 - Minimal Number of Coins for Change