The Coin Change Problem
Much like the Knapsack Problem we've looked at some time ago, the Coin Change problem is a classic problem in Computer Science, involving making change for a certain amount of money!
In this episode, we take a look at the basic, greedy version of the algorithm, and see how it fails. We then consider the straightforward recursive solution and note its inefficiencies, before going into the dynamic programming solution!
= CONTENTS PAGE =
0:00 Introduction
1:00 Definition of the Coin Change Problem
1:40 Simplistic Greedy Method
2:53 Greedy Method - Python Code
4:36 When the Greedy Method Fails
7:07 The Recursive Method
7:58 Recursive Method - Writing Python Code
13:52 Speed - The Problem with the Recursive Solution
14:50 The Dynamic Programming Method
15:32 Memo Table Contents
16:37 Memo Table - How to Use
21:20 Dynamic Programming Method - Full Trace
27:36 Dynamic Programming Code (Brief Look & Results)
28:48 Conclusion
= CODE DOWNLOAD =
To view and download the code written in this video, check out the following Bitbucket repository: https://bitbucket.org/nerdfirst/coin-...
To download, first click on "Downloads" in the left sidebar. Then, in the subsequent page, click "Download Repository".
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational YouTube channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → http://www.nerdfirst.net/donate/
0612 TV Official Writeup: http://nerdfirst.net/0612tv
More about me: http://about.me/lcc0612
Official Twitter: / 0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond YouTube videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! http://nerdfirst.net/
-----
Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.