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
talk to you guys again soon.
Không có nhận xét nào:
Đăng nhận xét