I took this problem from hackerrank. You can try it out yourself here. It's one of the canonical problems in dynamic programming and is commonly referred to as the coin change problem.
The problem is as follows:
You have a collection of coins, $C$, where each coin is of a different denomination. $C = [c_{1}, \cdots, c_{m}]$ where $m = |C|$.
You have an infinite quantity of each of these coins. You need to make change for some quantity $n$ with any combination and number of coins in $C$. The problem is to find all the ways you can make change for $n$.
For example, let $C = [1, 2, 3]$ and $n = 4$. We have a total of 4 different ways we can make change. Specifically, we can make change in the following ways:
c = [1, 2 ,3]
n = 4
In general, dynamic programming works by breaking up the overall problem into many smaller sub problems where we optimize each of the smaller sub problems so that we reach a optimal solution for the overall problem.
Let's be specific. In the above problem we can generalize our problem into two cases:
Let $i \in$ range(0, len(c)). For a given i, we either have:
For the first case, we cannot possibly make change for $n$ using the coin denomination specified by c[i]. So we can move on. For example, if you have to give someone \$5 you can't do it if you only have a \$10 bill.
For the second case, we know that we can make change for $n$ in at least as many ways as we could before the introduction of c[i]. Further, with the introduction of c[i] we can make change for $n$ using some combination of c[i] and the earlier denominations. Specifically, we need c[i] and $n$ - c[i] to make change for $n$. That is, we need to know how many ways we can make change for $n$ - c[i]. Here is the secret sauce! The essence of dynamic programming is breaking down the larger problem into a series of smaller problems. In this example, finding how many ways we can make change for $n$ - c[i] is the sub-problem.
Note, when n = c[i] we have to figure out how many ways we can make change for 0 cents. This is where our initial condition assumption comes into play, if we assumed that there is NO way to make change for 0 cents then we would always be under counting by 1 because we can always make change for n with one unit of c[i]. We need to count the null set as a valid set.
As you can see, the choice of initial condition is non-trivial and can lead to wrong results if we're not careful.
Now, let's look at some code.
dp = [1]+[0]*n
for i in range(len(c)):
for j in range(c[i], n+1):
dp[j]+=dp[j-c[i]]
print(dp[-1])
I'll break down the above code step by step:
In the first line, we initialize a list that keeps track of the number of ways we can make change for each incremental amount from 1 to n. Here, we the the number of ways of making change for 0 cents as 1.
In the second line, we loop over the elements in the list c, where c is the set of unique coin denominations.
In the third line, we loop over the elements in the dp list starting from the denomination specified by c[i] and ending at the amount that we have to make change for. Note that range(k,l) returns None when k > l so that our first rule above (c[i] > $n$) is implicitly incorporated in the code.
In the fourth line, we can see the logic in our second rule being implemented. dp[j] contains the number of ways to make change for j using the denominations before the introduction of c[i]. dp[j-c[i]] contains the number of ways to make change for j-c[i].
Finally, in the last line we return the number of ways to make change for $n$. This is the last element of the list by construction (the way we constructed dp).