How to stop shitting your pants when seeing a dynamic programming problem
--
Why would you want to get better with DP?
I have been struggling with DP forever. I just could not get it, so I just start to memorize common DP patterns for technical interviews because it’s not even that common, it shows up only 10% of the time.
One day I was having a mock interview and a DP problem showed up with a pattern that I never saw before, and the interview ended in the first 5 mins. Memorizing patterns makes it binary, it’s either you know the problem and just spet it out (which is not ideal but works), or you don’t know it and here you can not work with the interviewer or do anything, you will just say “I don’t know” and be a big zero.
So I knew this had to change. Even if it shows up 10% of the time, and you get around 10 questions during the whole process, so you WILL get one DP question and you’d better not be zero if you want to get a hire recommendation.
Why don’t you understand DP?
Simply, because most of the online content is bullshit. if you google any DP problem right now you will probably find a guy filling a table with a pattern that just magically appeared on the whiteboard. But actually, you will never care about filling that table when solving the problem.
if you open LeetCode discussion forms. you will find 5-line-ish solution with a list called “dp” that does not make any sense, you will try to make sense of it but you will fail, but guess what? it’s not supposed to make sense. This is the product, not the process. what you should learn is the process.
Before you learn dynamic programming
Before you learn dynamic programming you must be comfortable with recursion because guess what. DP is recursion. If you can solve the DP problem with a recursive approach you are 95% done with the problem.
Resources
As I said earlier, most of the content in this area is bullshit, so you gotta be careful because a bad resource does not only waste your time, but also confuses you. I would suggest you go for the following resources in order :
- If you have github students account you can access this Educative content for free
1- Recursion — hackerrank
2- First chapter of Dynamic Programming in Python — Educative
by now you should have a good idea of how to come up with a recursive solution and you need to practice
3- Solving Problems with Recursion in Python — Educative
slove as many problems as it takes for you to feel confident
4- Dynamic Programming in Python-Educative
come back to this course and solve all the problems as recursion problems, just recursion, pretend you don’t know anything about DP yet.
by now you should have had good understanding and practice about recursion
If you feel confident, move on to dynamic programming.
5- Dynamic programming — hackerrank
6- lectures 19,20,21 — MIT 6.006
now you watched, time to practice
7- Dynamic Programming in Python-Educative
go back to this course and solve all of the problems in top-down approach, which is basically saving the return of the recursive approach in a table
That’s already enough for technical interviews but why not go further?
8- Dynamic Programming in Python-Educative
go back to this course for the final time and read how you could turn the top-down approach to buttom-up one and get some practice
And there you go. You have the product (table) you saw on leetcode discussion form and youtube.
Coming up with the product from the process is straightforward but coming up with the process from the product is extremely tricky, isn’t it?
Now you have a process that you follow and you will give yourself and your interviewer a bigger chance to work together and come up with a solution even if you couldn’t do it on your own
