Coin sum problem – Dynamic Programming

Given a value n cents and m type of coins with values { c1, c2, .. , cm} cents each. How many ways can we make the n cents by using the coins as many times as you want?

For example, for n = 5 and C = {1, 2, 5}, there are 4 solutions {{1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}}.

We observe that we can solve this problem by solving the subproblem of finding solution for a lower sum. That is we can use a DP approach. We use DP when –

1. We can formulate the solution combining solutions of smaller subproblem, and.
2. There are overlapping subproblems.

Optimal Substructure
We can see that we can find the number ways we can make n using C={ c1, c2, .. , cm} coins by combining solution of making (n-cm) and including last coin cm to current solution; or we can simply ignore the last coin cm and try to find solution with remaining coins.

let, cs(C, n, m) be the number of solutions of making n using m coins C = {c1, c2, …, cm}. The we can write the following recursive formula,

cs(C, n, m) = cs(C, n-cm, m) + cs(C, n, m-1).

It is now clear that coin sum has a optimal substructure.

Overlapping Subproblems
If we write down the pictorial representation of the above recursion the we can see from the following figure that subproblems (such as cs({1,2},5,2) ) are getting repeated. That’s is we have overlapping subproblems and so we can use a table to store previous computation of solution to a sub problem.

                            cs({1,2,5},10,3)                     
                           /                \
                         /                   \              
             cs({1,2,5},5,3)                cs({1,2},5,2)
            /     \                          /         \
           /        \                       /           \
cs({1,2,5},0,3)  cs({1,2},5,2)        cs({1,2},3,2)    cs({1}, 5, 1)
  /               /     \                 /    \            /     \
/                /        \              /      \          /       \
        cs({1,2},0,2)  C({1},2,1)  cs({1,2},1) C({1},3) cs({1}, 4) cs({}, 5)
               / \         / \         / \        /     \    
              /   \       /   \       /   \      /       \ 
             .      .  .     .   .     .       C({1}, 3) C({}, 4)
                                               /  \
                                              /    \  


Below is a O(nm) solution for the coin sum problem using DP. 

public static int coinSum(final int[] coins, final int sum) {
    final int m = coins.length;
    final int[][] csTable = new int[sum + 1][m + 1];

    // base cases: if m == 0 then no solution for any sum
    for (int i = 0; i <= sum; i++) {
        csTable[i][0] = 0;
    }
    // base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
    for (int j = 0; j <= m; j++) {
        csTable[0][j] = 1;
    }

    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= m; j++) {
            // solutions excluding coins[j]
            final int s1 = csTable[i][j - 1];
            // solutions including coins[j]
            // look at the column index in csTable[i - coins[j - 1]][j]. This is not j-1 as we can use as much coin
            // of type j as we like.
            final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;

            csTable[i][j] = s1 + s2;
        }
    }

    return csTable[sum][m];
}

There could be another variant of this problem:

Given a non-negative number n. Find out how many ways n can be made by summing up non-negative integers.

This can be solved by coins sum problem as cs({0, 1, 2, …n-1}, n, n).