Coin Change Problem with Memoization and DP by Cracking the Coding Interview Author Tutorial Recommendation

The key to the coin change problem is Dynamic programming coin change with and without the coin. Start from bottom up rather than largest denomination to small. 

This is another coin change problem tutorial we recommend. This one is by Cracking the Coding Interview (the bible of coding interview) author Gayle Laakmann Mcdowell. The explanation is crystal clear and very helpful. The only thing it didn't cover in depth is the idea of using a coin (reduce sum) and withholding a coin (not reducing the sum) while increasing the index to process the next coin. This is also a memoization and dynamic programming problem.







Previously we recommended Coin Change problem by O'Neill Code. That one uses a bottom up greedy approach to solve for smaller denominations. Then add the ways up as approaching bigger denominations. http://www.siliconvanity.com/2017/11/coin-change-problem-dyanmic-programming.html

Tutorial highlights

Visualize using a coin versus not using a coin

Gayle Laakmann Mcdowell helps visualize using a coin vs withholding a coin.

Visualize the need for memoization

Using 50 cents is equivalent to using two 25 cents. The same sub problem appears when the original problem is reduced. Amount is now 29 cents. If we don't use dynamic programming we will be repeating work. 

Hacker Rank tutorial video coin change problem

Other tutorials that cover the coin change problem include Geek for Geeks, Interview Cake (there are some pluses and minuses, the variable names are a bit hard to read, but the code has a python version!). Most sample codes are in JAVA.