Scenario

In this activity, we will be building a dynamic programming algorithm to solve the coin change problem. Given a value, N, if we want to split it into coins, and we have an infinite supply of each of S={S₁, S₂, …, S_m} valued coins, in how many ways can we do it? The order of the coins doesn't matter. For N = 4 and S = {1, 2, 3}, there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, and {1, 3}, so the result should be four.

Aim

To solve the coin change problem as described previously using a dynamic programming algorithm.

Prerequisites

You need to implement the ways() method of the CoinChange class, which returns the number of ways to produce a given change for amount N, given a set of coins. It is available on the following path:

https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson4/activity/coinchange/CoinChange.java.

Steps for Completion

1. When going through a coin S_m, in order to count the number of solutions, we can divide the solution into two sets:
   • Those that do not contain any coin S_m
   • Those that contain at least one S_m
2. If w[i][j] counts the number of ways to make change for i using coins up to S_j, then we have the following recursion:

In this third and final section, we introduced the dynamic programming paradigm of algorithm design, using the 0-1 knapsack and the longest common subsequence problems as examples. We introduced the two properties a problem must observe to be optimally solved by a dynamic programming algorithm: optimal substructure and overlapping subproblems, and showed the students how to identify these properties. We've also seen the differences between a top-down (with memoization) and a bottom-up approach in dynamic programming algorithms.