In continuation with our journey through the infamous Blind 75 list of problems, today we are diving into the world of Dynamic Programming.
Think top-down. Code bottom-up. Always (Amit Agarwal)
For me, Dynamic Programming proves to be the most difficult form of interview questions. My biggest problem with it is to find a generalized approach to arrive at the solution effectively. Recognizing the need to solve a problem dynamically, can be a challenge in and of itself. Of course, we all know about the fibonacci sequence generation, or the stair stepper (which is the first problem we will discuss), these problems are easy to identify. Some other problems like coin change, can be fairly difficult to come up with the solutions on your own (much less in the allotted time during the interview process). My best suggestion is to know these listed problems below well, because they are the ones that have the highest chance to show up (or their slight variances).
That is enough with the intro! Let’s dive into the two different strategies of Dynamic Programming.
This Stack overflow post here explains quite well what are the differences between top-down vs bottom-up strategies.