Dynamic Programming

Pseudo-code

CHANGEDP(coin_array, change) {
    min_coins_used = [0,...,(change + 1)]
    min_coins_count = [0,...,(change + 1)]

    for coin in range(0,...,(change + 1)) {
        coin_count = coin
        latest_coin = 1

        for i in [coin_val in coin_array where coin_val <= coin]{
            if min_coins_count[coin - i] + 1 < coin_count {
                coin_count = min_coins_count[coin - i] + 1
                latest_coin = i
            }
        }
        min_coins_count[coin] = coin_count
        min_coins_used[coin] = latest_coin
    }

    min_count = min_coins_count[change]
    min_used = []

    for k in coin_array {
        min_used.append(0)
    }

    change_iter = change

    while change_iter > 0 {
        coin_val = min_coins_used[change_iter]
        p = 0
        for j in coin_array {
            if coin_val == j {
                min_used[p] += 1
            }
            p += 1
        }
        change_iter = change_iter - coin_val
    }

    return min_used, min_count
}

Runtime Analysis

The algorithm takes two inputs: coinArray and change. The parameter coinArray contains all of the possible denominations of coins that can be used to make change with. The parameter change is the amount of change that needs to be composed of various combinations of coins that are denoted in the coinArray. From this point forward we will refer to the length of the coinArray as $k$ and the value for change as $n$.

As can be seen from the pseudo-code above we first start with a for-loop that iterates from $0$ to $n$. Each change value between $0$ and $n$ are then checked against each denomination in the coinArray. This check occurs in the inner for loop where the values are from $0$ to $k$ in the worst case. We say worst case because if the change amount is less than any coin denominations within the coinArray then those coin denomination(s) are skipped within the loop. Therefore this portion of the algorithm will have a runtime of $O(n * k)$. The next for loop creates the min_used array and sets it to a length $k$ which will add a factor of $O(k)$ to the runtime. After that there is a while loop that runs similarly to the first nested for loop so it also will have a runtime of $O(n * k)$. The various variable assignments and index look-ups for the arrays within the method all will have $O(1)$. This leaves us with a runtime of:

Where the constant term $2$ drops off as well as the $O(k)$ and $O(1)$ terms because the $O(n * k)$ will dominate as $n$ becomes increasingly large. Therefore the finalized runtime of the dynamic programming change making algorithm is:

Dynamic Programming Table (Explained)

As described in the assignment, our dynamic programming approach uses table $T$ indexed by values of change 0, 1, 2, ..., A where $T[v]$ is the minimum number of coins needed to make change for $v$ and $T[0]=0$.

So how does our algorithm fill out this table $T$? Starting with $T[1]$ and increasing to $T[A]$ - using information already determined for smaller values of $v$, and considering the impact of adding one (and only one) additional coin from those available. This is best described by example.

In our example our coins are $[1, 5, 10, 25, 50]$ and we are trying to find $T[27]$. By definition we already know $T[0]$ thru $T[26]$. The available coins are 1, 5, 10, and 25. 50 isn't available because it's greater than 27.

So first we consider the coin with value of 1. We are adding this single coin to an existing pile of coins. Simple math tells us that because we are adding a single coin of value 1 to make 27 total, we must already have a total value of 26 prior to adding the coin. We can look up $T[26]$ because it's already been solved in a prior step. $T[26] = 2$ (a quarter and a penny), so a potential value of $T[27]$ is 3 (2 + 1). Before we declare $T[27]=3$ we need to check the other available coins for a smaller possibility.

Next we consider the coin with value of 5. By the same logic described above, because we are adding a single coin of value 5 to make 27 total, we must already have a total value of 22 prior to adding the coin. We can look up $T[22]$ because it's already been solved in a prior step. $T[22]=4$ (two dimes and two pennies), so another potential value of $T[27]$ is 5 (4 + 1).

Next we consider the coin with value of 10. By the same logic described above, because we are adding a single coin of value 10 to make 27 total, we must already have a total value of 17 prior to adding the coin. We can look up $T[17]$ because it's already been solved in a prior step. $T[17]=4$ (a dime, a nickle and two pennies), so another potential value of $T[27]$ is 5 (4 + 1).

Finally we consider the coin with value of 25. By the same logic described above, because we are adding a single coin of value 25 to make 27 total, we must already have a total value of 2 prior to adding the coin. We can look up $T[2]$ because it's already been solved in a prior step. $T[2]=2$ (two pennies), so another potential value of $T[27]$ is 3 (2 + 1).

Therefore, looking at the minimum possible values we declare $T[27]=3$. This method of filling out $T(v)$ is valid because it considers and compares the impact of adding 1 coin of each available value at all steps while taking into account the prior known minimum coins for lesser values of $v$.