The problem requires to count number of coin changes for a particular cost.
For example, if I have coin values of 50, 20, 10, 5, 1, I can form costs of:
5 => (5), (11111), which are 2 ways.
10 => (10), (5, 5), (5, 11111), (11111, 11111), which are 4 ways.
Here is my function. It is returning wrong results begging from cost of 10 (returns 9 ways while the actual number of ways is only 4)
int dp[10000];
int coins[] = { 50, 20, 10, 5, 1 };
int rec(int n)
{
if (n == 0) return 1;
if (dp[n] != -1) return dp[n];
int cnt = 0;
for (int i = 0; i < 5; i++)
if (coins[i] <= n) cnt += rec(n - coins[i]);
return dp[n] = cnt;
}
How can I fix this function to give the correct number of ways? Is this algorithm correct even? see the complete code and its output here
NOTE: my problem is not with dp array initialization. I am using memset to initialize it to -1 each time before calling rec.
(5, 1, 1, 1, 1, 1) and (1, 1, 1, 5, 1, 1) is different way in you algorithm, you should keep it decreasing.
int dp[10000][5]; // dp[20][2] means, if the biggest coin is coins[2],
// how much ways for 20 ?
int coins[] = { 1, 5, 10, 20, 50 }; // here
int rec(int n, int m)
{
int cnt = 0;
int i;
if (n == 0) return 1;
//if (m == 0) return 1;
if (dp[n][m] != -1) return dp[n][m];
for (i = 0; i <= m; i++)
if (coins[i] <= n) cnt += rec(n - coins[i], i);
return dp[n][m] = cnt;
}
int main()
{
memset(dp, -1, sizeof(dp));
printf("%d\n", rec(10, 4));
}
The result is wrong since you never make sure that your algorithm starts with the 5 coin. (5,11111) is just as valid in your code as (1, 5, 1111), but this is the same result. Your result should be wrong from 6 and higher, not 10 and higher.
To fix this you can do like a cutoff in your function rec():
int rec(int n, int cutoff)
{
if (n == 0) return 1;
if (dp[n] != -1) return dp[n];
int cnt = 0;
for (int i = cutoff; i < 5; i++)
if (coins[i] <= n) cnt += rec(n - coins[i], i);
return dp[n] = cnt;
}
Should do it.
Edit: you will have to take care of your dp[] array, since it does not care about this cutoff, but this in general is the fault you are running into. You could comment that line, and check if this works.
One remark: Your initialization
memset(dp, -1, sizeof dp);
is not really safe. memset initializes every byte of a memory space (see http://www.cplusplus.com/reference/clibrary/cstring/memset/.). For this particular case you are lucky and the representation of int(-1) is (probably) the same of four times unsigned char(-1).
I would suggest using std::fill ( http://www.cplusplus.com/reference/algorithm/fill/ ).
