I was asked a DP question in an interview for a startup whose name is a substring of mathematician and I failed cause I didn’t know DP. Whenever I Google Dynamic Programming tutorials, they show me this stupid Fibonacci Sequence tutorial that never helped me extrapolate the idea to the more challenging problems. I consider this article as revenge against DP and also as an unofficial tutorial for those still struggling.
Qn. If you have 4 types of coins, and the value of each type is given as [2, 3, 5, 6] respectively, how many ways can you make change for 10?
Ans. 5 ways. (Work it out in a paper to convince yourself)
This becomes a daunting combinatorial problem for a human being as the amount and/or the number of denominations increase. Fortunately, computers are willing to do the heavy lifting for us. When I saw this question the first time I felt hopeless and skipped it and kept skipping it whenever I encountered it until I had to face it in the interview.
Time to rip it apart.
Definitions: required amount → N (10$), list of coin denominations → COINS [2, 3, 5, 6]
Let’s tackle the obvious. If N is in COINS, there’s at least 1 way to make the change. ‘At least’ is key here, because 6 itself can be made otherwise by {2, 2, 2} and {3, 3}. We’ll use this information later.
Consider that you ought to pay me 10$ with coins of the above denomination. You look through your wallet and put a 6$ on the table. Next, with the remainder 4 at the back of your mind, you start searching again. You see a 3$ next. But you wouldn’t take it because you can’t make 4 with 3 and any other coin in COINS. Ultimately you’ll end up with {2, 2, 6} as the change.
Imagine had you begun with a 5$ on the table as the initial coin, you’d have taken the 3$ you encountered next and then a 2$ to end up with {2, 3, 5}.
If you think about it, the first coin you choose (6$) reduces the initial N (10$) by its value and now you are at the same problem but with a different N of 4$. Also the different ways you can build the change actually branch out based on your initial coin.
If you think we need to use recursion, you are correct. No brownie points for you though.
num_ways(10) = num_ways(4) + num_ways(5) + num_ways(7) + num_ways(8)The recursive function looks as follows
def num_ways(x):
if x < 2: return 0 # base case
ways = num_ways(x-6) + num_ways(x-5)
+ num_ways(x-3) + num_ways(x-2)
if x in c: ways += 1
return waysNow, if you are screaming why are you teaching me recursion, I came here for DP, I hear you. DP is just an efficiency hack on recursive algorithms. Consider the term corresponding to 7, it will call the following,
num_ways(7) = num_ways(1) + num_ways(2) + num_ways(4) + num_ways(5)You see num_ways(5) both in num_ways(10) and num_ways(7). This is called an overlapping subproblem, a common jargon used in DP. In general, num_ways(x) where x < N almost always gets called more than once.
You know what Dynamic programming says? Just store the solution to the subproblem in an array or something the first time you compute it so that the next time the function is called just look up the array.
def num_ways(x):
if ways[x] is NULL:
ways[x] = do_recursive_call()
return ways[x]That is all about Dynamic Programming. The struggle here is to get the recursive definition right along with a solid base case and to store the results efficiently.
Some Extras.
There is an alternative to what we just did and is considered superior by CS people because recursive calls have a stack limit and these problems tend to exceed them even with our new found trick of storing the answer. They call what we did as a top-down approach (or) memoisation. Because we start with what we want and go down and down to solve the smaller subproblems.
The favoured bottom-up approach is if we want num_ways(N) find num_ways of 1 → N-1 first and then calculate num_ways(N). This iterative method won’t overflow the stack because while finding for N you have all values till N-1 so all you’ll be doing is look up and adding. No branching recursions occur saving us overflow errors or function call overheads.
Even more Extras.
If you are like me and already have your suspicions of duplicates in this recursive definition. Yes, you are right. But what might be the duplicates?
Consider case 3$ + num_ways(7) which are {3} + {2, 2, 3} and {3} + {2, 5}. Now, what prevents 2$ + num_ways(8) from including {2} + {3, 5} which is just a permutation of {3} + {2, 5}.
How to prevent duplicates ?! Essentially we don’t want both {2, 3, 5} and {3, 2, 5} to be valid. Easy hack, don’t allow the function to use coins of value lesser than the first coin, which forces the function to chose only solutions which are sorted, making {2, 3, 5} valid but {3, 2, 5} invalid.
num_ways(10, [2,3,5,6]) = num_ways(4, [6]) # used 6$, so can't use 2$ or 3$ or 5$
+ num_ways(5, [5, 6])
+ num_ways(7, [3, 5, 6])
+ num_ways(8, [2, 3, 5, 6]) # used 2$, so can use 2$, 3$, 5$ as-well
Thanks for reading and hope you understood, at least vaguely. The code in python is added as a gist. Fill the comments with doubts/better explanations/errors if I have made any.
References
