Project Euler Solution #31: Coin sums

This problem is a typical case of dynamic programming. Let's follow the normal way of solving such a problem; we identify a small sub-problem and build a table for all possible values. When we begin with 1p, how many ways are there to change it with 1p coins, 2p coins and so on? 1p can be expressed by only one 1p coin:

With a 2p coin and so on is it not possible to express the amount. However, we want to calculate the number of ways we can express the target value with, so we include the lower coins for each column and express the maximum number of possible ways in each cell:

This table means that there is only one way to express 1p, no matter what coins are being used. When we go on, we can continue with two pence:

With only 1p coins, 2p can be expressed with 1p+1p. 2p can be expressed with a 2p coin as well, which gives 2 possibilities, but with all additional coins the result remain the same. We continue this pattern for 3, 4 and 5 pence:

Now that we have an intuition of the table creation process, we can draw some conclusions. The first conclusion is that the first column is always one, meaning that there is only one way to form a target \(n\) with the use of \(n\) times 1p coins.

The second conclusion is that we always walk from left to right. If the corresponding coin fits into the target amount we build the value of the cell by adding the number of ways we can form the target without using the coin (the cell to the left) plus the number of ways we can form \(\text{target}-\text{columnValue}\), i.e. the number of ways to form the remainder if we subtract the coin from the target. If the corresponding coin does not fit, we just copy over the value from the cell to the left.

As an example take the last line with target 5p. The first column is 1 as stated before and the second column is \(\text{target}-\text{columnValue}=5p-2p=3p\), which we already have calculated. That means we can simply lookup the value from the table, which is two here. This algorithm can now be implemented quite easily in JavaScript:

function solution(target) {
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];
  var table = new Array(target + 1);
  for (var i = 0; i <= target; i++) {
    table[i] = new Array(coins.length);
    table[i][0] = 1;
  }

  for (var i = 0; i <= target; i++) {
    for (var j = 1; j < coins.length; j++) {
      table[i][j] = table[i][j - 1];
      if (coins[j] <= i)
        table[i][j]+= table[i - coins[j]][j];
    }
  }
  return table[i-1][j-1];
}

This approach works totally fine and computes the results within miliseconds. But the solution isn't perfect yet. We can turn the bottom-up approach into a top-down approach and skip a table creation. All that is needed is a 1d array, and we create column after column in-place, since we only depend on smaller values that are calculated earlier. At the end the array will represent the last column of the table. So how do we get to the solution? For ease of use we define 0p to be 1, which makes it easier to lookup direct coin-changes without a hard-coded check and as arrays are zero-indexed anyway this makes the algorithm even smoother. After that we start with a 1p coin. As before, we can express any amount exactly one time with 1p coins:

When we go ahead and focus on a 2p coin, we can't make changes for any value less than 2p. But for any other target value, we can create the difference of the target value and the coin value 2p. That means we take away 2p and lookup the rest in the table, which is lower than 2p and is already known. After we go through all possible target values this way, we get:

At the end we only have a 5p coin. Using it, we can skip all values below 5p again. But 5p itself can be expressed by one more 5p coin, which results in the final table:

So what we did here is, we ran over all coins. For each coin value, we started with the current value and went to the target value. Each entry of the array is then the previous value plus the number of ways the amount can be expressed, when the coin value is already excluded. When implemented, this results in the following pretty piece of code:

function solution(target) {
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];
  var table = new Uint32Array(target + 1);
  table[0] = 1;
  for (var i = 0; i < coins.length; i++) {
    for (var j = coins[i]; j <= target; j++) {
      table[j]+= table[j - coins[i]];
    }
  }
  return table[target];
}

It's fun to see that two derivations result in a pretty similar implementation. Only the loops are swapped and matrix preparation is a bit different.