What's up everyone? Sam here from www.byte-by-byte.com and today I'm going to show you guys how to identify when to use dynamic programming in your coding Interviews. Dynamic programming is something that scares a ton of people and I think that a big part of why people get so scared is that they don't even know when to use dynamic programming in the first place.

So in this video I'm going to talk about two different ways that you can identify when to use dynamic programming for a problem. So the first way is maybe the obvious way is to see whether or not a problem actually aligns with the definition of dynamic programming. And if you're not sure about the definition of dynamic programming you really need to check out my ebook, but to just briefly recap dynamic programming problems are problems that have optimal substructure and overlapping subproblems.

So what do those mean? Optimal substructure means that you can break a problem down into smaller and smaller chunks and then combine those together to get the optimal solution. And if that sounds super familiar to you then that's probably because it's basically recursion. So more or less what we're saying is that if we can solve a problem recursively then it has optimal substructure.

The other component is overlapping subproblems and this is the part where dynamic programming really shines. Overlapping subproblems just means that we're recomputing the same thing more than once and dynamic programming works by caching those values so that we don't actually have to recompute multiple times and we can just compute every value once.

So if we see that a problem has these two properties then we know that we can use dynamic programming. And the best way to see if a problem has both these properties is to actually draw a picture. And by drawing a picture, I mean you're gonna draw a tree sort of like this one that you can see and you are going to draw out all of the recursive functions. In this we can actually see how there are multiple nodes in the tree that have the same values which means that they're overlapping subproblems and we can see because it's recursive that has optimal substructure and so we know that we can use dynamic programming for this problem.

Now this is kind of a lot of work, right, because you have to go through the whole definition you have to define the function and everything so what if there was an easier way for us to identify when to use dynamic programming? Or at least give us a little better sense? And luckily there are two heuristics that I've come up with that make it a lot easier to decide whether to even consider going down this path or not.

The first heuristic is does the problem involve maximization, minimization, optimization, or counting? And what I mean by this is let's consider finding the shortest path through maze. That would be a minimization problem. If we wanted to find the lowest number of coins that it would take to make a given amount of change that's also a minimization problem. If we wanted to find the longest path through a maze for whatever reason that would be a maximization problem. Or if we just want to find the best or worst or if we want to find the total number of paths through a maze these are all examples of what I'm talking about and if you see one of these things then there's a good chance that you might want to use dynamic programming.

And the corollary to this which is the other heuristic is: If you can solve a problem by enumerating all the different possible solutions and finding the best one then it's likely a good candidate for dynamic programming. So let's go back to our maze example because it's just a really good example for these sorts of problems. Let's say we wanted to find the shortest path through maze. One thing that we could do is just find every possible path through the maze and then pick the shortest one. It would be super easy to do that and by having that heuristic, granted with mazes there are better ways that we could do this we could use breadth-first search, but having those heuristics makes it much easier for us to identify whether we even want to consider using dynamic programming.

So that's all I got for you guys today if you like this video please subscribe below and don't forget to sign up for my ebook at dynamicprogrammingbook.com if you haven't already and get that ebook downloaded so that you can learn even more of this stuff about dynamic programming and use it effectively in your interviews. And I’ll talk to you guys again soon.

How to recognize a dynamic programming problem

The hardest part of DP isn’t solving it — it’s realizing you’re looking at a DP problem in the first place. Two characteristics give it away:

• Optimal substructure — the best solution to the whole problem is built from the best solutions to its smaller subproblems. If you can define the answer in terms of the answers to smaller versions of the same problem, that’s a strong DP signal.
• Overlapping subproblems — as you break the problem down, you keep solving the same smaller subproblems over and over. (This is the key difference from divide-and-conquer, where the subproblems are all unique.) When you spot repeated work, that’s your cue to cache results — i.e., use DP.

There’s also a dead giveaway in how these questions are phrased. If a problem asks for the number of ways to do something, the maximum or minimum of something, or whether something is possible — and your brute force solution explores a tree of repeated choices — it’s almost always a dynamic programming problem.

Once you’ve recognized it, the approach is always the same: write the brute force recursive solution first, notice the repeated subproblems, then memoize. For the full walkthrough, see my guide to recursion and why you should always start with a brute force solution.