Skip to content
  • Courses
  • Resources
  • Blog
  • About
Menu
  • Courses
  • Resources
  • Blog
  • About
STUDENT LOGIN
  • Courses
  • Resources
  • Blog
  • About
  • Student Login
Menu
  • Courses
  • Resources
  • Blog
  • About
  • Student Login

When should I solve a problem using dynamic programming

  • April 30, 2018

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.

DON'T DO ANOTHER CODING INTERVIEW...

...until you've mastered these 50 questions!

GET YOUR FREE GUIDE

RECOMMENDED ARTICLES

data structures

Article

The Definitive Guide to Data Structures for Coding Interviews

Data structures are critical to coding interview success. In this post, I'll show you exactly which data structures you need to know to nail your interviews.

Article

Acing the Google Interview: The Ultimate Guide

Acing the Google interview. Every engineer's dream. But the Google interview is really hard. In this post, you'll learn exactly how to prepare effectively.
stuck on coding interview

Article

10 ways to get unstuck and never fail another coding interview

It happens time and again. People fail coding interviews because they don’t know what to do when stuck on a problem. Developing a clear plan of attack helps you to succeed at any whiteboard coding interview.
Envelope Twitter Facebook Linkedin Youtube

© Byte by Byte 2016-2022

Privacy Policy

Terms and Conditions

Earnings Disclaimer

What if coding interviews were easy?

Sounds impossible right? It’s not!

Let me show you the RIGHT way to study for interviews so you can ace your Google Interview without breaking a sweat.

Download my FREE guide to the 50 most common coding interview questions asked at companies like Google, Facebooks, and Amazon.

Download my FREE guide to the 50 most common coding interview questions asked at companies like Google, Facebooks, and Amazon.

Get fully prepared for your Coding Interview and save 20% with Exponent. Learn More  →