coin change recurrence solution

Question

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?

Answer 1

I don't really understand your recurrence relation:

Let dp[i][j][k] represent sum up to i with j elements and k coins.

I think you're on the right track, but I suggest simply dropping the middle dimension [j], and use dp[sum][coinsLeft] as follows:

dp[0][0] = 1  // coins: 0, desired sum: 0  =>  1 solution
dp[i][0] = 0  // coins: 0, desired sum: i  =>  0 solutions

dp[sum][coinsLeft] = dp[sum - S1][coinsLeft-1]
                   + dp[sum - S2][coinsLeft-1]
                   + ...
                   + dp[sum - SM][coinsLeft-1]

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):

public static int combinations(int numCoinsToUse, int targetSum, int[] denom) {
    // dp[numCoins][sum]  ==  ways to get sum using numCoins
    int[][] dp = new int[numCoinsToUse+1][targetSum];

     // Any sum (except 0) is impossible with 0 coins
     for (int sum = 0; sum < targetSum; sum++) {
         dp[0][sum] = sum == 0 ? 1 : 0;
     }

     // Gradually increase number of coins
     for (int c = 1; c <= numCoinsToUse; c++)
         for (int sum = 0; sum < targetSum; sum++)
             for (int d : denom)
                 if (sum >= d)
                     dp[c][sum] += dp[c-1][sum - d];
     return dp[numCoinsToUse][targetSum-1];
 }

Using your example input:

combinations(2, 4, new int[] {1, 2, 3} ) // gives 2