Introducing Dynamic Programming

[00:00:02]
>> Bianca Gandolfo: So dynamic programming is a optimization technique. We talked a little bit about optimization earlier in this workshop and we did a couple different caching exercises. So cue that up in your brain because this is gonna build on top of that, and it's also gonna build on top of our previous example of make change, with all of those recursive calls in a brute force solution.

[00:00:27]
So you may remember that,
>> Bianca Gandolfo: We're doing a lot of calculations, repeated calculations, right, for our make change. I painted this, by the way, cuz I'm a nerd. We have a lot of repeated calculations. And so what dynamic programming says is if you can break it into the subproblems and the subproblems are optimal, meaning that they are going to give you the correct answer, you can cache these values.

[00:01:10]
Just like we did with the factorial, with the memoize for the factorial, that's secretly a dynamic programming solution. And so the reason it's called dynamic programming, which is not really reflective of what it is, is kinda similar to why JavaScript is called JavaScript and it's nothing to do with Java.

[00:01:31]
It's kinda like a marketing thing, and these really smart people take advantage of the fact that their management doesn't really understand what they do. And so dynamic programming, they chose the name dynamic programming because it was making some government grant maker more likely to give them funding to continue their research.

[00:01:51]
And then JavaScript, the reason that we call it JavaScript is because it kind of, Java was really in. And we wanted to make it seem like, JavaScript's kinda like Java, we're cool too. So there's kind of,
>> Bianca Gandolfo: I don't know, I just think of it as deceptive marketing to either convert people to supporting a programming language or get someone to give you money so you can keep researching this mathematical concept as you please.

[00:02:25]
And here we have the name Dynamic Programming. You could think of it as just caching. If you have a solution that you can cache, that's dynamic programming. So there is a couple of ways that you can cache your solutions. So we have a top-down recursive approach, which is what we've been doing a lot of, where we start from, say 12, right, which sort of our end result.

[00:02:54]
And then we break it up into smaller pieces and we cache if we recalculate something, right? And so that's a top-down recursive technique. And then there's also a bottom-up iterative technique, where you can translate the recursion into an iterative solution, starting from the simplest problem, which would be make change 0.

[00:03:25]
So start with make change zero, you calculate that. Make change one, you calculate that. You cache it. So if it comes up again, you then just have it on hand. So one starts from the top and goes down, the other one starts from the bottom and goes up, and it's iterative.

[00:03:45]
And so that's really the key to dynamic programming, it's just this memoization step. So all the stuff that you did in the memoization and caching part of this workshop is all related to dynamic programming. And it's kind of intimidating, and I don't think the thing that's intimidating about dynamic programming is necessarily the memoization step.

[00:04:08]
I think that the hard part about the dynamic programming is actually the recurgent involved in reasoning about these subproblems, and being able to trace our minds through how our code executes to solve these problems. And so the way to get through that really is through practicing recursion, and better improving your mental model of how your code executes, doing things like the call stack game on your own, or talking, rubber ducking we call it, where you just talk out loud about what your code is doing.

[00:04:38]
Again, I think an anti-pattern in learning is to type something, hit play, see what happens. We can do that really easy in JavaScript, right, we just refresh and we hit Enter in that console. Versus like in compiling, which you kinda have to wait a little longer and maybe you're less tempted to make these shortcuts.

[00:04:55]
But really being able to reason through what you're writing versus just having your execution environment tell you if you have an error or if your solution isn't what you expect. So pro tip. What else do I wanna tell you about dynamic programming? Question?
>> Speaker 2: Do interviewers, when you are in an environment where you're on a computer doing the interview, do interviewers kind of watch for how many times you try to just run the code instead of understanding what can [CROSSTALK]?

[00:05:29]
>> Bianca Gandolfo: You can't run the code actually. So in a typical interview environment, you aren't running the code, you're either writing it on a whiteboard or you're doing it in something like a Google Doc. You might even do it in text editor, but not typically in an environment where you can run it.

[00:05:43]
So it's not that they're not looking for it, it's like you don't really even have that available to you. And so you need to learn how to debug your code in your head. And so how you do that is you just choose some inputs, make sure your inputs aren't too simple because sometimes the simple inputs can hide edge cases, so a pretty complex input.

[00:06:04]
And run that, just like we're doing that call stack game, but maybe you don't have to do the call stack part if it's not recursion. So that's one way to go about manually debugging, and I think that's the best practice. Even though at first it may seem like a waste of time, it may seem like it's taking longer to go through these problems, in the end, you'll be better for it.

[00:06:30]
Yeah, cool, okay, good questions. Any other questions?
>> Bianca Gandolfo: All right, so the difference between dynamic programming and a divide and conquer technique is that the dynamic programming has overlapping subproblems. So when we're doing make change, for example, there are many times that we're calculating, like make change of five, that's always gonna be the same answer.

[00:06:59]
Versus our merge sort example, where that merge step isn't overlapping, each step has to be done individually and it's gonna change every time. And so that's what I think about when I think about the difference between dynamic programming, and divide and conquer. They're still recursive approaches, but one of them has some repeated calculation that you can cache and access, while one of them you can't, you have to just go through it each time.

[00:07:30]
Dynamic programming problems are also really common with really big, like Google is really famous for asking dynamic programming problems. So if you are studying to go, you wanna work at a big company or something like that, I would focus mostly on dynamic programming, especially cuz it can be tough to do it within a certain timeframe while you're under pressure.

[00:07:54]
So I would definitely practice these.