How To Spot Dynamic Programming Problems

so your interviewer just asked you a dynamic programming question don't worry I got you but to do a dynamic programming question you have to be able to identify when to actually use dynamic programming hello I'm Tara I'm a senior software engineer and I used to teach computer science at Carnegie Mellon so all dynamic programming problems are conceptually recurrent that means that the solution to the big problem can be built from solutions to the smaller subproblems and just to drive that home I'm gonna put that right here not every recursive problem is a dynamic programming problem so not all recursive problems can use DP we have factorial versus Fibonacci and both of these are conceptually recurrent but only one of them is a dynamic programming problem let's take a look at factorial first as a quick reminder factorial of 4 is 4 * 3 * 2 times one what is the recurrence for factorial of n well it's actually n times factorial of n minus 1 so when we solve factorial of n or in this case factorial of 4 we make a bunch of recursive calls right to solve factorial of 4 we have to also solve factorial of three and to solve factorial of three we have to solve factorial of two and to solve factorial of two we have to solve factorial of one so Fibonacci is a little bit different so it starts with zero and then it goes one these are our two base cases so the zero Fibonacci number is zero and the first Fibonacci number is one the second Fibonacci number would be adding those two together so also one and then the third Fibonacci number is adding those two together that's two and the fourth Fibonacci number is adding those two together that's three so on and so forth what is the recurrence for Fibonacci of N so Fibonacci of N is actually equal to Fibonacci of n minus 1 plus Fibonacci of n minus 2 so to solve Fibonacci of 4 we have to do Fibonacci of 3 plus Fibonacci of 2 so then to solve Fibonacci of 3 well then we actually need to bring in Fibonacci of 2 again that's actually a hint and Fibonacci of one and then to solve Fibonacci of two we need to take Fibonacci of 1 and then Fibonacci of 0 here's another hint um and Fibonacci of zero give me a second to draw the arrows okay so Fibonacci of 1 is a base case and Fibonacci of 0 is also a base case but we actually still need to do some work here for Fibonacci of 2 so excuse me factorial I need to get you out of the way for a second so we got another fib of 1 and another fib of 0 coming your way okay so this is what our final tree looks like you'll notice something really interesting we do a lot of duplicate work we're computing Fibonacci of 2 2 times we're computing Fibonacci of 1 3 times and Fibonacci of 0 2 times if we were asking for Fibonacci of a really big number this would actually be quite cumbersome we'd be doing so much duplicate work the key to recognizing that this is a dynamic programming problem is noticing that there are overlapping sub problems that is the key overlapping sub problems really hammer this home by pointing out that these are all overlapping let me color them purple if you look at factorial in comparison once we compute factorial of 3 we never use it again same with factorial of 2 same with factorial of 1 this is the key for recognizing a dynamic programming problem a dynamic programming problem is noticing that there are overlapping sub problems that is the key overlapping sub problems this video is already getting long so I'm gonna show us how to actually write the code for dynamic programming there are a few different ways of doing it and yeah tune in for that video next