Pseudo-Code for Coin Change

To implement the coin change problem, we'll resort to dynamic programming. The big idea is to solve smaller sub-problems and store their results to be used later. For example, in the previous example, we solved the smaller sub-problem for denomination 2, 6, 8 by using just coin {2}. Let's think about our solution:

1. There are as many levels in the tree as the number of coins
2. We need the solution for denominations (1 .. amount)
3. The next level requires the solution from the previous level

The best thing to do is to define an array matrix M, that stores the intermediate results. The size of the matrix is then N * (amount+1), whereN=number of unique coins and amount=denomination.

We have (amount+1) for simplicity so that an index value denotes a denomination and as the indices start from zero, we need (amount+1) columns. Initially, we set only the cells of M, whose column index is an integer multiple of coin[i]. For example, In the given problem, we'll fill M[0][2] by 1 (as one {2} is needed to make 2), M[1][6] by 2 (as {3, 3} is required to make 6). We can follow this pattern for the final solution.

xxxxxxxxxx

// Fill the array using the following rule.

​

Routine: Solve

Input: Coin array of size N, denomiation amount

Required for intermediate results: Matrix M of size Nx(amount+1)

​

Base case:

1. For all rows with column index j=0, set M[i][j]=0

2. For each row i=0..(N-1)

    a. If a column index (j>0) is an integer multiple of coin[i], i.e., if (j mod coin[i] == 0) 

        then M[i][j] = j/coin[i]

        else M[i][j] = inf

Recursive case:

1. for each row i=1..(N-1)

    a. for each col j=0..amount

            i. M[i][j] = min(M[i-1][j-k*coin[i] ]+k), where k is 0..floor(j/coin[i])

2. return M[i-1][amount]