Dynamic Programming Introduction Introduction
We remember the getting our first Lego set like it was yesterday. It was love at first glance through the Toys "R" Us window: there was something about that cool, pixellated version of a scene that told us we had to buy the kit and rely heavily on the instructions to make our own, unique version.
(If Lego ever decided to expand to the furniture business, Ikea would have serious competition.)
It all went very well at first, until we looked in the box and found all those separate baggies. What was the point of those baggies? Why not just put all the Legos in one box and be done with it? We tore them all open and dumped them in the middle of the living room to get started on that masterpiece.
That's when things went south.
How were we supposed to know you're supposed keep the baggies of parts separated until you need them? Nobody warned us; we blame Legoland and its unclear labels.
In any case, after several agonizing hours of studying the instructions and sifting through the Lego pile for that tiny round peg, we finally managed to put together our Women of the Supreme Court set (complete with Sandra Day O'Connor, Ruth Bader Ginsburg, Sonia Sotomayor, and Elena Kagan)—plus or minus a couple pieces.
Just…try not to breathe on it, okay?
Yup, we were pretty proud of ourselves until that annoying neighbor kid showed us the working Ferris wheel they somehow built out of the same set. (Not that the female Supremes wouldn't want to decide on important cases in their courtroom, but it would be nice to take them out to the state fair and have some fun every once in a while.)
Some people are just too smart. Not that we're bitter about it. They probably can't flip their eyelids inside out or belch-talk lines from Dr. Seuss books.
We all have our gifts.
Speaking of gifts, all that Lego work was basically like dynamic programming (DP for those of us in the know). That's right: Legos are educational toys…unless you just chew on them or try stuffing them up your nose. Dynamic programming is all about
- breaking overwhelmingly massive problems down into more manageable chunks (let's call them sub-problems, or sub-assemblies, or something like that).
- solving the sub-problems (usually recursively, but sometimes not).
- figuring out how to use the sub-problem answers to get the solution to the overwhelmingly massive problem.
That's just like a Lego set with separate baggies for the sub-assemblies. As long as you don't just dump everything into one overwhelmingly massive pile of tiny bits, you have much more manageable problems that you can build to solve a problem.
Dynamic programming uses principles of optimization to avoid using huge amounts of CPU time when you need many, many, many iterations or calls to imbedded functions or procedures. Yep, 'many, many, many' is a totally-scientific and legitimate way to talk about runtimes in the exponential worst case scenarios.
If there's no way to break a problem down into repeatable sub-problems, then dynamic programming isn't the way to go. You'll just have to find something less dynamic.
If multiple repeating sub-routines are your thing, then come on in and enjoy some optimized redundancy.
Why Should I Care?
Computers used to be slow. Like, take ten minutes just to connect to the internet slow. Email moved slightly faster than actual mail, but not by much. Nobody expected computers to be fast because…they had never seen a fast computer.
Now you'll see people cursing when their favorite classic-novel-turned-YouTube-series takes an extra second to load. Hey, it's frustrating; we get it.
Dynamic programming (DP) is all about using computers more efficiently so you don't have to freak out and throw your phone at a wall. Pro tip: if you want to speed up your phone, throwing it at any hard surface doesn't solve the problem.
Computers need memory or space to store variables and calculate results for the program to use later. When programs execute, they use CPU (central processing unit) time, but they only get so much space to work.
That's where dynamic programming comes in.
Just like how you closely guard personal free time so you can make the most of that time spent browsing Nail Art on Pinterest, programmers think about how best to use the Central Processing Unit time to make sure they don't spend hours doing something. Each computer only has one CPU. When a program uses CPU time, the computer can't do anything else. If you can minimize the amount of CPU time a program uses, you can move on to other programs much faster and do other things.
Like refresh your YouTube subscription page. Or read the book that YouTube series is based on.
Compared to the CPU, computers have tons of storage space. If you can save a little of that data in a less expensive place, it makes a huge difference.
It's like when your mom says you have to clean your room, even though it's only been two or three years since the last time you cleaned it. You go out and buy a couple of those plastic storage bins, pack as much stuff as you can in them, and then shove them in your closet. Bam. Room clean.
Once you've loaded those bins, it doesn't cost you anything to leave them sitting in your closet. They can stay there a day, a week, or a year without you needing to lift a finger. It only costs you when you have to take something out or put something else in. Between those times when you need to grab or put something away, though, they can just hang out without you needing to do anything.
You can add more storage space to your computer, sure, but you only have one CPU driving program execution. Just like you, that CPU can only do one thing at a time, so its time is valuable. Don't even start debating about how you can do multiple things at one time. That has been scientifically disproven.
So there.
Tl;DR: CPU time is way more important than memory, so you want to do whatever you can to move things to memory when you can. That means using—wait for it—dynamic programming.