Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.There is additional restriction though: you can only give change with exactly K coins.
For example, for N = 4, k = 2 and S = {1,2,3}, there are two solutions: {2,2},{1,3}. So output should be 2.
Solution:
int getways(int coins, int target, int total_coins, int *denomination, int size, int idx)
{
int sum = 0, i;
if (coins > target || total_coins < 0)
return 0;
if (target == coins && total_coins == 0)
return 1;
if (target == coins && total_coins < 0)
return 0;
for (i=idx;i<size;i++) {
sum += getways(coins+denomination[i], target, total_coins-1, denomination, size, i);
}
return sum;
}
int main()
{
int target = 49;
int total_coins = 15;
int denomination[] = {1, 2, 3, 4, 5};
int size = sizeof(denomination)/sizeof(denomination[0]);
printf("%d\n", getways(0, target, total_coins, denomination, size, 0));
}
Above is recursive solution. However i need help with my dynamic programming solution:
Let dp[i][j][k]
represent sum up to i
with j
elements and k
coins.
So,
dp[i][j][k] = dp[i][j-1][k] + dp[i-a[j]][j][k-1]
Is my recurrence relation right?
I don't really understand your recurrence relation:
I think you're on the right track, but I suggest simply dropping the middle dimension
[j]
, and usedp[sum][coinsLeft]
as follows:The answer is then to be found at
dp[N][K]
(= number of ways to add K coins to get N cents)Here's some sample code (I advice you to not look until you've tried to solve it yourself. It's a good exercise):
Using your example input:
combinations(2, 4, new int[] {1, 2, 3} ) // gives 2