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.

Analysis: 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: we can add a coin with value v₁ into a set of coins whose total value is t-v₁. The minimal number of coins to get value t-v₁ is f(t-v₁). Similarly, we can add a coin with value v₂ into a set of coins whose total value is t-v₂. The minimal number of coins to get value t-v₂ is f(t-v₂)…

Therefore, we divide a problem to calculate f(t) into n sub-problems: f(t-v₁), f(t-v₂), …, f(t-v_n). We can get a formal equation for f(t) as the following accordingly:

 

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;

}

Also refer to http://oucsace.cs.ohiou.edu/~razvan/courses/cs4040/lecture19.pdf
Read full article from Coding Interview Questions: No. 26 - Minimal Number of Coins for Change