Dynamic Programming, a bitter pill to swallow
While preparing for the interviews, one of the toughest topic that took a lot of my time was dynamic programming, after struggling for weeks I got some insides of how dynamic programming work, so here are few suggestions that i would like to give to people who are starting with DP:
- NEVER START DIRECTLY WITH TOP DOWN APPROACH
While solving DP problems what mistake most people do is to start directly with writing or figuring out the top down approach for the problem, this is a bad approach and most of the time you will not be able to reach the solution for the problem
2. DP IS NOTHING BUT ADVANCED RECURSION
DP is highly related to recursion or many may argue that DP is derived from recursion, so one of first thoughts that should come in mind while solving the DP problems is to think about how the problem can be solved using recursion, after solving the problem using recursion then only you should try to memorize it or try to implement the top down approach.
3. MEMOIZATION OF RECURSION AND TOP-DOWN GIVES THE SAME TIME COMPLEXITY
This is my personal opinion and you may not agree with it, but what i have observed is mostly the memoization solution of recursion passes all test cases and mostly does not give stack overflow error, so if during an exam if you are stuck with getting the DP solution you may submit the memoization version, it will also pass all test cases
4. PATTERNS ARE EVERYWHERE
Finding patterns with in the questions are important for not only DP but all type of coding problems, most of the questions asked during interviews are a variation of a parent problem, so finding that parent problem comes with practice.
This is the first of many articles that i will be writing on DP and on coding in general, thanks for reading the whole article, if you like the article please give a follow or pin me on linked-in it motivates me a lot.
