Problem: Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi 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 v1 into a set of coins whose total value is t-v1. The minimal number of coins to get value t-v1 is f(t-v1). Similarly, we can add a coin with value v2 into a set of coins whose total value is t-v2. The minimal number of coins to get value t-v2 is f(t-v2)…
Therefore, we divide a problem to calculate f(t) into n sub-problems: f(t-v1), f(t-v2), …, f(t-vn). 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;
}Read full article from Coding Interview Questions: No. 26 - Minimal Number of Coins for Change