The Dynamic Programming Template [Technique Tuesdays]

How you can slay the boogeyman of your Leetcode journey

Oct 18, 2023

Hey, it’s your favorite cult leader here 🦹‍♂️🦹‍♂️

On Tuesdays, I will cover problem-solving techniques that show up in software engineering, computer science, and Leetcode Style Questions📚📚📝📝.

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

Help me buy chocolate milk

p.s. you can learn more about the paid plan here.

It’s been a while since we’ve done a Leetcode Template article, so it would be nice to go back to the good ol’days. But don’t worry, as always, the article will go beyond Leetcode. In this article, I will give you the math behind DP, so you can implement it as when you need it.

At it’s core, Dynamic Programming (DP) is a powerful technique used to solve a specific kind of problem: those that can be broken down into simpler sub-problems. These sub-problems are solved individually, and their solutions are stored, rather than being recomputed, to achieve an efficient overall solution. Thus, we will build our template to leverage a similar principle- figure out the recursive sub-structure, attack the smaller computations, and use those to build upon the bigger ones.

I’m experimenting with AI Generated Images for an upcoming piece. So far I’m not impressed. Wanted to know how y’all have felt.

How to solve Dynamic Programming Problems

Identify the DP Problem: As with most cases, recognition is half the battle. Recognize if the problem can be broken down into overlapping subproblems and if the optimal solution can be constructed efficiently from its subproblems. Classic examples of this include the Fibonacci sequence, shortest paths in a graph, or the Knapsack problem. Often you will be able to catch the DP-ness of a problem when you start playing with toy cases and building up from there. What also helps is developing skills in adjacent areas- specifically looking through the recursive function template over here (this will get you good with recursive problems in general) and this piece on spotting Greedy Algorithms (I see it as a first-cousin).
Choose a Memorization Technique: If you’re sufficiently good at the foundations of DP, then most problems don’t require you to do many mental gymnastics for the implementation. By breaking down the structure, you can hit most of the points. So once you have identified DP being the way forward, it makes sense to look into how you want to build it.
- Top-Down with Memoization: Start solving the problem by breaking it down. If you see that the problem has overlapping sub-problems, store the results in a table (generally implemented as an array or some sort of map), and refer to this table whenever you need the result again.
- Bottom-Up with Tabulation: Start with the simplest possible version of the problem and solve it. Then, use this solution to build up solutions to bigger and bigger versions of the problem. Store solutions in a table as well. Some purists consider this to be superior, but I personally believe that you should go with whatever you find easier.
If you’re good enough you can directly code and test things out. However, I like to go through the next steps just to show off my theoretical knowledge and organized problem-solving skills. If you’re struggling w/ DP, then explicitly going through these steps can help you rewire your brain. Eventually, you might speed-run this, but for now taking this slow might help you. When I first started wrestling, I had to think about the feint, penetration step, drive, and finish individually. Now, I can play/skip steps and still finish things because of the intimacy I built up. Similar principles applies.
Define the State: Think about what states can define the problem. For instance, in the knapsack problem, the state might be defined by two parameters: the remaining weight and the number of items left to consider. This step is helpful for narrowing your focus, preventing you from being overwhelmed/shut down. It also directly tells you what you should be storing. If you’re really struggling, sketch out a brute-force recursive solution to help you identify what variables you want your state to track (that’s why it’s such a common-step in the solutions I go over).
Formulate the State Transition Equation: Once you've defined the state, think about how you can transition from one state to another and establish a relationship. For instance, for a Fibonacci sequence has the recurrence relationship:
```
dp[i] = dp[i-1] + dp[i-2]
```
This tells you that tracking 2 previous numbers would be worthwhile.
Define the Base Cases: Every DP solution (and recurrent solns in general) requires one or more base cases. For the Fibonacci sequence, the base cases are:
```
dp[0] = 0, dp[1] = 1
```
This with the state-transition equation (which sets up your recursion) will be good enough for proceeding with the code.
Implement, Test, and Optimize: Now, you can go ahead and implement your DP solution. Once you’re good with the basic implementations, it’s worthwhile to study space and time optimization techniques, such as reducing the space complexity by using variables instead of full-fledged arrays.

With these steps, your Leetcode supremacy should only be a few months away. I look forward to hearing about your results.

That is it for this piece. I appreciate your time. As always, if you’re interested in working with me or checking out my other work, my links will be at the end of this email/post. If you like my writing, I would really appreciate an anonymous testimonial. You can drop it here. And if you found value in this write-up, I would appreciate you sharing it with more people. It is word-of-mouth referrals like yours that help me grow.

Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!

Using this discount will drop the prices-

800 INR (10 USD) → 640 INR (8 USD) per Month

8000 INR (100 USD) → 6400INR (80 USD) per year (533 INR /month)

Get 20% off for 1 year