To see how the elements of dynamic programming come together in a real problem, let’s explore the classic dynamic programming problem Coin Change (LeetCode 322).
The problem: Given a set of integer coin denominations and an integer amount, return the fewest number of coins that make that amount, or -1 if there is no solution.
Optimization
In dynamic programming, the word programming refers to mathematical optimization. For this problem, we are trying to minimize a value, the number of coins.
Subproblems
To apply dynamic programming, we need to break the problem into subproblems. Here’s how we can do that for Coin Change.
Let $f(a)$ be the minimum number of coins from the set ${c_0, c_1, …, c_{n-1}}$ required to make amount $a$. So our program needs to calculate $f(a)$ given $a$ and a set of $c_i$ denominations.
Suppose we know the value of $f(a-c)$, the number of coins required to make $a-c$, where $c$ is one of the coin denominations. Given this result for the amount $a-c$, we can add one more coin, $c$, to get our target amount $a$. This means $f(a) = f(a-c) + 1$. We knew how many coins were optimal to make the amount $a-c$, and by adding one more coin, we have the minimum number of coins required to make the amount $a$. That’s the solution to the problem.
To find $f(a-c)$, we can apply the same approach: suppose we know $f(a-c-d)$, where $d$ is a coin from the set (possibly another coin with value $c$). If we keep subtracting coin values, we’ll eventually get to one of the base cases: either $f(0) = 0$ (since it takes no coins to make an amount of $0$), or $f = -1$ for negative amounts (since we can’t make those).
Calculating the optimal $f(x)$ for some $x < a$ is a subproblem of the original problem of calculating $f(a)$.
Optimal substructure
The fancy term optimal substructure means that once we break the problem down into subproblems and find optimal solutions to those subproblems, we can use those solutions to calculate the optimal solution to the original problem. Think of it this way: if we know $f(a-c) = v$ is optimal, then $f(a) = v+1$ is also optimal, since we can’t add less than one coin. If we get from $f(0) = 0$ to $f(a) = v+1$ and we use an optimal result at each step, then our overall solution will also be optimal.
Overlapping subproblems
The overlapping subproblems requirement means that as we break the problem down into subproblems, the same subproblems come up repeatedly. If we found that there were as many distinct subproblems as there were unique combinations of coins, then it wouldn’t matter that we could use those subproblems to find $f(a)$. Our algorithm would be no more efficient than an exhaustive search. Dynamic programming is only useful if we repeatedly come across the same $x$ values. After calculating $f(x)$ once, we can store the result and re-use it in the future.
Memoization
The process of storing answers to subproblems is called memoization (yes, the ‘r’ is omitted). This is the process that makes dynamic programming efficient. If we can look up an $f(x)$ result in $O(1)$ time and calculating $f(x)$ would take more than $O(1)$ time, then it’s worth storing the result.
Algorithms and data structures
The dynamic programming process doesn’t dictate a particular algorithm or data structure. But dynamic programming uses algorithms and data structures. For Coin Change, the data structure is just an array, and the algorithm is just a loop and a recursive call. (The recursive implementation isn’t the only way to implement a dynamic programming solution, but it matches the way I defined the subproblems above).
Implementation
Our recursive function accepts as parameters the coin list, the current amount, and the memoization table. First, we handle the base cases: amount is negative, amount is zero, and amount is already calculated. Then we iterate through each coin denomination and recursively find the result for amount - coin (the current amount, excluding the coin we’re trying). For each of these results, we can get the solution for amount by adding $1$ — i.e., we can add the current coin to the amount and increase the coin count by $1$. If the recursive call returns $-1$ (meaning no valid solution), we can ignore it. If the result is not smaller than the current coin count, we can also ignore it, since we need the optimal solution. If it passes those two tests, then it is the optimal count.
Once we try all the coins, we can update our memo table with the optimal count (or $-1$ if we didn’t find a valid count) and return the result for that amount.
To start the recursive process, our main program will call coinChangeHelper with the input coin array, the target amount, and an empty integer array of size amount + 1 (the + 1 is because we need dp[0] to be 0 and we need dp[amount] to store the answer).
Here is a pseudocode version of this implementation:
int coinChangeHelper(int[] coins, int amount, int[] dp)
if amount < 0, return -1 // can't make negative amounts
if amount == 0, return 0 // no coins required to make 0
if dp[amount] != 0, return dp[amount] // look up the result
count = MAX_INT // sentinel value
for each coin in coins
// recursively get the result without the current coin
result = coinChangeHelper(coins, amount - coin, dp)
// if the result is valid and optimal, add 1 (the current coin)
// to get the new result
if result >= 0 and result < count
count = result + 1
// we didn't find a valid count
if count == MAX_INT, dp[amount] = -1
else dp[amount] = count
return dp[amount]
See ElementNotFoundException’s solution on LeetCode for a Java implementation of this recursive solution.
For an iterative implementation, see my previous article LeetCode 322: Coin Change.
Why greedy doesn’t work
People familiar with real-world change-making might wonder why we can’t just sort the coin list in descending order and use as many coins of each denomination as possible from largest to smallest. To see why this doesn’t work, try using the coin list ${5, 4, 1}$ to make the amount $8$. The greedy algorithm would start by using the $5$ coin, and then would have to use three $1$ coins, for a count of $4$ coins ($5 + 1 + 1 + 1 = 8$). The dynamic programming algorithm would find the optimal solution of just two denomination $4$ coins ($4 + 4 = 8$).
(Image credit: DALL·E 3)
For an introduction to this year’s project, see A Project for 2024.