Dynamic programming: coin change

Dynamic programming might seem like something advanced and complicated. While it in fact produces efficient solutions it’s just another approach to problem solving.

The last problem: DP: Coin change was difficult for me to solve.

At first I tried to use the same approach I’ve used for tribonacci numbers (with modification that ways[i] = ways[i-coin1] + ways[i-coin2] + ...). The problem here is that we are looking at combinations, not permutations of different coins. So 1, 2, and 3 is the same as 3, 2, and 1.

Next thing I’ve tried was recursion. If you call recursion only for coins of greater or equal value then there will be no permutation and the answer will be correct.

All possible combinations from coins 1, 2, 3 of length 4.

This solution wasn’t accepted due to timeout. And it makes sense. We have some duplicate computations there: for instance last 3 numbers 2–3–3 or 2–2–2.

I’ve tried to come up with some solution but wasn’t able to do it in more than 1 hour. Then I went to “discussions” page and the solution was right there and it was only 10 lines of java code.

In solution we create array of length n+1 (same as for tribonacci) and then walk through each coin value. For each coin value we run a loop starting from coin value and till the end where we set ways[i] += ways[i-coinValue]. That’s it. That way we don’t count 3, 3, 5 and 3, 5, 3 as different ways.

When outer loop is done our correct answer is located at ways[n].