Dynamic programming is a method by which a solution is determined based on solving successively similar but smaller problems. This technique is used in algorithmic tasks in which the solution of a bigger problem is relatively easy to find, if we have solutions for its sub-problems. 

The Coin Changing Problem

For a given set of denominations, you are asked to find the minimum number of coins with

which a given amount of money can be paid. Assume that you can use as many coins of

a particular denomination as necessary. The greedy algorithmic approach is always to select

the largest denomination not exceeding the remaining amount of money to be paid. As long

as the remaining amount is greater than zero, the process is repeated. However, this algorithm

may return a suboptimal result. For instance, for an amount of 6 and coins of values 1, 3, 4,

we get 6 = 4 + 1 + 1, but the optimal solution here is 6 = 3 + 3. 

The following table shows what dynamic programming does with the denominations, 1, 3 and 4 and the total amount to be paid of 6:

There is a column header and a row header. The column header has the numbers, 0, 1, 2, 3, 4, 5, and 6. These are all the possible amounts to be paid, which are integers from 0 to 6 (inclusive). Dynamic programming breaks the 6 to be paid into all the possible smaller amounts to be paid of 0, 1, 2, 3, 4, 5, and 6. These 7 targets form the smaller similar problems to be solved successfully to obtain the final result for 6. 

The row header has all the different possible combinations of the given denominations. It begins with the empty set, ∅ (also written as {}). The different combinations as sets, follow in order, beginning from the smallest denomination.

With dp[i,j], dp stands for dynamic programming. i is a row index. j is a column index. That is, dp[i,j] is the two-dimensional array, for the table. Each entry in the table is identified by array element, dp[i,j]. 

Explanation of the Table

A dynamic programming algorithm finds solution to this problem for all amounts not exceeding the given amount, and for increasing sets of denominations. For the example data, it would consider all the amounts from 0 to 6, and the following sets of denominations: ∅, {1}, {1, 3} and {1, 3, 4}. Note: ∅ is for row 0; {1} is for row 1; {1, 3} is for row 2; and {1, 3, 4} is for row 3.

Let dp[i, j] be the minimum number of coins needed to pay the amount j, if we use the set containing i denominations. The number of coins needed must satisfy the following rules, whose explanations are given after (refer to the above table while reading the rules): 

1) no coins are needed to pay a zero amount: dp[i, 0] = 0 (for all i);

2) if there are no denominations and the amount is positive, there is no solution; so for convenience the result can be infinite in this case: dp[0, j] = ∞ (for all j > 0);

3) if the amount to be paid is smaller than the highest denomination c_i , this denomination

can be discarded allowing the rule: dp[i, j] = dp[i − 1, j] (for all i > 0 and all j such that c_i > j, which is same as j < c_i); this rule does not apply to row 0 (zero based index) after column 0 (zero based index); dp[i − 1, j] is the cell directly above the cell in question;

4) otherwise, we should consider two options and choose the one requiring fewer coins: either we use a coin of the highest denomination, and a smaller amount to be paid might remain, or we don’t use coins of the highest denomination. That is, either we use the highest denomination for the row (and a smaller amount to be paid might remain, and be found on the left of the same row), or we use rule 3 above; whichever gives the smaller number of coins. The rule here is dp[i, j] = min(dp[i, j − c_i ] + 1, dp[i − 1, j]) (for all i > 0 and all j such that c_i ≤ j). That is, when c_i ≤ j, the highest denomination or rule 3 is used; whichever gives the smaller number of coins.

The above 4 rules constitute the algorithm for this dynamic programming. The explanation (illustration) follows: 

Point 1: Note that the problem has been broken down into smaller problems of paying the amount of 0 or of 1 or of 2 or of 3 or of 4 or of 5 or of 6. When the amount to be paid is 0, no coins are needed. So all the entries in the first column are zero. dp[i, 0] = 0 (for all i).

Point 2: If an amount of 1 or 2 or 3 or 4 or 5 or 6 has to be paid, but there are no denominations (no money corresponding to row 0 for the empty set), then there is no solution. For convenience and to differentiate the entries of row 0 from the entries of column 0, each entry of row 0, except the first, is given the value, infinity (∞). dp[0, j] = ∞ (for all j > 0). Infinity is actually an unimaginably large number. 

Row 1: For row 1, there is only one denomination, which is 1. dp[1,0] has already been taken into account in point 1, and it is 0. For one to be paid, one 1 is needed. For two to be paid, 2 ones are needed. For three, 3 ones are needed. For four, 4 ones are needed. For five, 5 ones are needed. For six, 6 ones are needed. C_i here is 1. So, rule 4 above where c_i ≤ j is applicable here – see below.

Point 3 (rule 3): For row 2, the set is {1, 3} and c_i = 3. For point 3, j < c_i . When the amount 1 is to be paid, the denomination 3 cannot be used, so the denomination, 1 is used once; this is dp[i − 1, j], from cell above in same column. When the amount 2 is to be paid, the denomination 3 cannot still be used, so the denomination, 1 is used twice, making the number of coins, 2 here; this is dp[i − 1, j], from cell above in same column.. The amounts of 1 and 2 are less than 3. The value for c_i here is 3, the highest value in the set {1, 3}. 

Point 3: For row 3, the set is {1, 3, 4} and c_i=4. When the amount 1 is to be paid, the denomination 4 cannot be used, so the denomination, dp[i − 1, j] becomes applicable and 1 is used once, making the number of coins, 1 here. When the amount 2 is to be paid, the denomination 4 cannot be used, so the denomination, dp[i − 1, j] becomes applicable and 1 is used twice, making the number of coins, 2 here. When the amount 3 is to be paid, the denomination 4 cannot be used, so the denomination, dp[i − 1, j] becomes applicable and 3 is used once, making the number of coins, 1 here (and not three 1's). The value for c_i here is 4, the highest value in the set {1, 3, 4}, and not 3.

Point 4: Now, when the amount 3 is to be paid, for row 2, the denomination 3 is used, and it is used once, instead of the denomination, 1 being used three times increasing the number of coins, instead of reducing the number of coins. For point 4, c_i ≤ j, that is j ≥ c_i . There is a choice to be made here. The choice is between using 1 three times and using just 3 once. Seen another way, the choice is between the value which is in the cell dp[i − 1, j] just vertically above the current cell, and the value in the cell dp[i, j − c_i] plus 1, where c_i in this case is 3, the highest denomination in the set {1, 3}. Here, the condition for the column index is c_i ≤ j being 3 ≤ 3; and the row index is i = 2. So the choice is between 3 of dp[1,3], and 1 from value in dp[2,0] plus 1 = 0 + 1 = 1. Remember that these values are number of coins. So the answer is 1, for minimum number of coins. 

point 4: When the amount 4 is to be paid, for row 2, the choice is between four ones, for four coins, and a 1 and 3, for two coins. 1 and 3 for two coins, which is the minimum number of coins, is chosen. For point 4, c_i ≤ j, that is j ≥ c_i . Seen another way, the choice here is between the value which is in the cell (dp[i - 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j - c_i]) plus 1, where c_i in this case is 3. Here, the column index is j = 4, greater than 3; and the row index is i = 2. The column condition here is c_i ≤ j = 3 ≤ 4. When the denomination, 3 is chosen, the smaller amount remaining is in cell j – c_i = 4 - 3 = 1 plus 1. So the denominations used are 3 and 1: two coins (content of dp[i, j − c_i ] + 1).

Point 4: When the amount 5 is to be paid, for row 2, the choice is between five ones, for five coins, and two ones and 3, for three coins. Two ones and 3 for three coins, which is the minimum number of coins, is chosen. For point 4, c_i ≤ j, that is j ≥ c_i . Seen another way, the choice here is between the value which is in the cell (dp[i - 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j - c_i]) plus 1, where c_i in this case is 3. Here, the column index is j = 5, greater than 3; and the row index is i = 2. The column condition here is c_i ≤ j = 3 ≤ 5. When the denomination, 3 is chosen, the smaller amount remaining is in cell j - c_i = 5 - 3 = 2 plus 1. So the denominations used are 3 and 1 (and 1): three coins (content of dp[i, j − c_i ] + 1). 

Point 4: When the amount 6 is to be paid, for row 2, the choice is between six ones, for six coins; and two threes for two coins. In terms of number of coins, the other options (three ones and one 3, for four coins; and two ones and one 4, for three coins) are in-between these limits. Two threes for two coins, which is the minimum number of coins, is chosen. For point 4, c_i ≤ j, that is j ≥ c_i . Note that there are four options here, and not just two. However, the code deals with two options. Seen another way, the effective choice here is between the value which is in the cell (dp[i − 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j − c_i]) plus 1, where c_i in this case is 3. Here, the column index is j = 6 greater than 3; and the row index is i = 2. The column condition here is c_i ≤ j = 3 ≤ 6. When the denomination, 3 is chosen, the smaller amount remaining is in cell j - c_i = 6 - 3 = 3 plus 1. So the denominations used are 3 and 3: two coins (content of dp[i, j − c_i ] + 1).

Point 4: Now, when the amount 4 is to be paid, for row 3, the denomination 4 is used, and it is used once, instead of the denomination, 1 being used four times increasing the number of coins, instead of reducing the number of coins; or instead of using one 1 and one 3 to have two coins, which is still not good enough (two is higher than 1). There is a choice to be made here. The three options are: four coins (four 1’s), two coins (1 and 3), or one coin (just 4). However, the code deals with two options. For point 4, c_i ≤ j, that is j ≥ c_i . Seen another way, the effective choice here is between the value which is in the cell (dp[i − 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j − c_i]) plus 1, where c_i in this case is 4. Here, the column index is j = 4; and the row index is i = 3. The column condition here is c_i ≤ j = 4 ≤ 4. j - c_i = 4 - 4 = 0. The number of coins in cell dp[i, j − c_i] is 0, and plus 1 gives 1. The choice is between the content of cell dp[i − 1, j] , which is 2, just vertically above the current cell, and the value in the cell dp[i, j − c_i] plus 1; minimum is 1. So the denomination used is 4: one coin. 

Point 4: When the amount 5 is to be paid, for row 3, the choice is between five ones, for five coins, and two 1’s and 3, for three coins, and one 1 and 4 for two coins. One 1 and 4 for two coins is chosen, for minimum number of coins. There are three options here. Seen another way, the effective choice here is between the value which is in the cell (dp[i − 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j − c_i]) plus 1, where c_i in this case is 4. Here, the column index is j = 5, greater than 4; and the row index is i = 3. The column condition here is c_i ≤ j = 4 ≤ 5. When the denomination, 4 is chosen, the smaller amount remaining is in cell j - c_i = 5 - 4 = 1. So the denominations used are 4 and 1: two coins.

Point 4: When the amount 6 is to be paid, for row 3, the choice is between six ones, for six coins; three ones and one 3 for four coins; two ones and one 4, for three coins; and two threes for two coins. Two threes for two coins is chosen, for minimum number of coins. There are four options here. However, the code deals with two options. Seen another way, the effective choice here is between the value which is in the cell (dp[i − 1, j]) just vertically above the current cell, and the value in the cell (dp[i, j − c_i]) plus 1, where c_i in this case is 4. Here, the column index is j = 6, greater than 4; and the row index is i = 3. The column condition here is c_i ≤ j = 4 ≤ 6. The minimum number of coins is 2, of cell dp[i − 1, j] , which is cell dp[2,6]. 

Point 4: Rule 4 (point 4) means choose between the value which is in the cell dp[i − 1, j] just vertically above the current cell, and the value in the cell dp[i, j − c_i] plus 1. If the maximum denomination for the row is chosen, then the remaining value is on the left of the same row. 1 has to be added to this remaining value, which has already been assessed to be minimum for j - c_i , in order to have the effective remaining value.

Implementation

Consider n denominations, 0 < c₀ ≤ c₁ ≤ . . . ≤ c_n−1 . The algorithm processes the respective denominations and calculates the minimum number of coins needed to pay every amount from 0 to k. k is the highest amount to be paid. When considering each successive amount, we use some previously calculated results for the minimum number of coins. 

There are k + 1 columns because of the preceding zero column, for zero amount to be paid. There are n + 1 rows, because of the preceding empty set, for row 0.

The code of interest in the function of interest, begins with the creation of the 2D array (vector) and initializes all the elements to 0. This means that all the elements in the first column have been made zero. Next, the infinity elements in row 0 after column 0, are given the infinity value. 

There is an outer for-loop that iterates over all the elements for the denominations (rows). Inside this for-loop is nested two for-loops in parallel (one then the other). The first for-loop implements rule 3 for each row, and puts values in the cells from column 1 to just less than column c_i (c_i > j). The next for-loop implements rule 4 for each row, continuing just after where rule 3 stopped, for that row, and puts values in the cells from column c_i to the end of that row (c_i <= j). It is assumed that all the denominations in the denominations array (vector), are there in ascending order. The program is (read the code and comments):

<script type='text/javascript'>
    "use strict";
    
    function dynamic_coin_changing1(C, k) {
        let n = C.length;

        const rows = n+1;
        const cols = k+1;
        const dp = [];
        dp[0] = []; 
        dp[0][0] = 0;
        for (let p=1; p<k+1; p++)  dp[0][p] = Infinity;
        for (let i = 1; i < rows; i++) {
            dp[i] = []; 
            for (let j = 0; j < cols; j++) {
                dp[i][j] = 0;    //initialize each cell to 0
            }
       }

        //effective dp programming begins here
        for (let i=1; i<(n+1); i++) {
            for (let j=0; j<C[i - 1]; j++)    // C[i - 1] is maximum C for the row
                dp[i][j] = dp[i - 1][j];
            for (let j=C[i - 1]; j<(k + 1); j++)
                dp[i][j] = Math.min(dp[i][j - C[i - 1]] + 1, dp[i - 1][j]);
        }

        return dp;
    }

    const C = [1, 3, 4];
    const res = dynamic_coin_changing1(C, 6);
    for (let i=0; i<res.length; i++) {
         for (let j=0; j<res[i].length; j++) {
             document.write(res[i][j] + ' ');
         }
        document.write('<br>');

    }
 
</script>

The output is:

0 Infinity Infinity Infinity Infinity Infinity Infinity
0 1 2 3 4 5 6
0 1 2 1 2 3 2
0 1 2 1 1 2 2 

In the code, c_i = C[i – 1]. This is because of zero based indexing for the denominations. For the set {1}, the number of elements is 1, and so 1 is at index noOfElements - 1 = 1-1 = 0. For the set {1, 3}, the number of elements is 2, and so 3 is at index noOfElements - 1 =  2-1 = 1 . For the set {1, 3, 4}, the number of elements is 3, and so 4 is at index noOfElements - 1 =  3-1 = 2 .

Since there is an added row for the empty set, of the number of denominations, the number of rows for the denominations, becomes zero based. And so, in the code, c_i is the value in C[i – 1], where C is the array (vector) of denominations. 

The actual question was to find the minimum number of denominations, for a given set of denominations, that 6 could be paid with. So the real answer is 2 (bearing in mind that 3, 3 are the denominators). In this case, the cell for row n and column k has the required 2; that is, cell [3,6] with zero based indexing.

Time and Space Complexity

Both the time complexity and the space complexity of the above algorithm is O(n · k), where the dot means times. Space complexity refers to the number of (different) variables used. The time complexity ignores the time to create and initialized to zero, the two dimensional array, whose time complexity is somewhat O(n · k), though much less than the official O(n · k). The official time and space complexity is given for the combined for-loops. n refers to the number of rows and k refers to the number of columns. 

In the above implementation, memory usage (space complexity) can be optimized (reduced). Notice that, during the calculation of dp, we only use the previous row, so we do not need to remember all of the rows, in two dimensions. This means that only one one-dimensional array (vector) has to be created, with all elements initialized to zero.

Both inner for-loops above iterate a row, with the second for-loop completing the row. The first inner for-loop iterates from 0 to just before C[i – 1]. The second inner for-loop iterates from C[i – 1] to the end of the row. The two for-loops can be combined into one for-loop, with their internal codes combined into 1. A program that reduces the space complexity from O(n . k) to O(k), ignoring the additional 1 in k+1 column number, is: 

<script type='text/javascript'>
    "use strict";

    function dynamic_coin_changing2(C, k) {
        let n = C.length;

        const dp = new Array(k+1).fill(0);
        for (let p=1; p<k+1; p++)  dp[p] = Infinity;

        //effective dp programming begins here
        for (let i=1; i < n+1; i++) {
            for (let j=C[i - 1]; j < k + 1; j++)
                dp[j] = Math.min(dp[j - C[i - 1]] + 1, dp[j]);    //re-writes row
        }

        return dp;
    }

    const C = [1, 3, 4];
    const res = dynamic_coin_changing2(C, 6);
    for (let i=0; i<res.length; i++) 
        document.write(res[i] + ' ');
    document.write('<br>');
 
</script> 

The output is:

    0 1 2 1 1 2 2

which is the last row of the 2D array (vector). 

Time and Space Complexity for the dynamic_coin_changing2() Function

The space complexity for the dynamic_coin_changing2() function, is O(k). The time complexity remains at O(n . k). This time complexity still ignores the time to create and initialized to zero, the one dimensional array (vector).