Introduction to Dynamic Programming: React Edition
So you are a react developer, trying to make the leap from the beautiful world of states, effects, and contexts to the competitive world of competitive programming(yes, I know how it sounds) or the scary world of FAANG interviews. Well, worry not as with this article I’ll try to make the transition easier for one of the most important topics for the said competitive and scary worlds — Dynamic Programming.
There are a lot of articles on the internet that discuss the basics of Dynamic Programming(for the sake of reducing redundancy, let’s just call it DP moving forward) and they do it pretty well. So what’s the need for another article well it’s the lack of connecting the theory of DP with one of its most impactful real-world implementations — React.
I have tried to set this article apart from the plethora of Introductory Articles on Dynamic Programming and hence used React related concepts when possible to explain things when I can. Hence basic knowledge of react and it’s hooks(specially — useState and, useEffect) is a must. Awareness of React.memo is a plus point but not necessary as it will be covered at the end.
Content to be covered
Personally, I like to know beforehand what topics I’ll be going through when I read an article, that way I can skip to the part that I need and save some time. So I am gonna list the content here, feel free to skip ahead if you like chaos.
- Recursion and Memoization
2. Dynamic Programming and how to identify it
3. Important Terminologies
4. Example with Fibonacci series and some good problems
5. Relation with React
Recursion and Memoization
Recursion, in simple words is a type of process in which a function keeps on calling it self until a break condition is encountered. It is mostly used to write cleaner code.
Memoization on the other hand is an optimization technique to prevent expensive function to run again with the same parameters. Just like useEffect, which when passed with an dependencies array depending on a variable selectedTags won’t be called until selectedTags is updated.
Dynamic Programming and how to Identify it
So basically when you solve a solution recursively you are often re-calculating the values for the same ’x’, now as you can tell this is way too slow for large problems. Hence to optimize it, we add memoization to it so that computation for a specific ‘x’ is only performed once and then re-used.
In a nutshell DP is the mixture of Recursion and Memoization.
A problem must contain the following traits to be solved by DP:-
1. It should have recursion, with at least 2 calls to itself.
2. It should be an optimal type of problem.
If it satisfies only 1, then it might or might not be DP.
Optimal types of problem include the cases where you have to find min, max, high and low types of things. For example, if you are asked to find the shortest distance from A to B then it’s a DP problem.
After these two steps, you should try to 1st memoize the solution and then move on to tabulation(more on it in Important Terminology).
Example With Fibonacci Series
To keep the article simple, I would like to discuss the easiest implementation.
As you can see that major part of the program is same(the recursion part), the only change is the addition of a memo list that stores the result of previous computations
Great, since you understood this you can look into some more beginner problems like:-
- 0–1 and Unbounded Knapsack(Basically a bag)
- Min Steps to Convert a number to 1 using only division by 2,3 and subtraction by 1.
Solutions to these are available on the internet.
And once you are done with this you can move towards advanced problems like matrix chain multiplication and more.
Important Terminologies
Top-Down Approach
It is the approach that we have been following till now, i.e recursion. So basically you start from the top where you have your desired ’n’ and keep coming down with problems that have lesser computation time. Along with that we keep storing the values of those operation so that they don’t have to re-calculated.
Here we can store the values of fib(1,2,3) for re-use.
But Keep in mind, you have to make sure to not re-calculate the value of an already computed computation.
Bottom-Up Approach
As you might have guessed, this approach is the exact opposite of Top-down approach. So instead of starting from the top it starts from the base condition and moves up to the desired ’n’, here you don’t have to worry about if an operation for a certain ’n’ has already been calculated or not. Can you guess why? Because we are following a serial(sort of) approach.
For example, if the state of your react application depends on the previous state you don’t have worry about the previous value, instead you can easily get access to it from parameter in the setState’s callback.
Tabulation
This is the method of implementing Bottom-Up approach in DP. In this we draw a table that helps us in writing a recursion-less code and hence helps in avoiding the in-famous StackOverflowError. The table is filled with keeping the base conditions in mind and the last cell is our ans. Now the table is mostly a 2-D table, which looks something like this…
But for the sake of introduction only, I’ll stick to a single row. Here, you can see that F(1) is needed to calculate F(2), F(2) to calculate F(3) and so on.
Relation With React
Now that you have understood a bit about DP, I’ll tell you it’s relation with React and how you can relate the concepts between the two.
Let’s revise react’s fundamentals a bit with the terminologies we just learned. So as you can see in the following tree data is passed in Top-Down approach, i.e, the components at the root level are rendered before the components below them and the events are passed from the bottom most component to the root level in bottom-up approach.
Also let’s revisit react’s render process, so whenever a parent component’s props changes all the child component in it are re-painted to the DOM. Now it’s now uncommon for a parent level context to have same props as before, for example let’s say you have a list with various pokemons in it and when ever you click on it you are taken to detail page.
So it is possible for a user to change the pokemon twice or thrice, which means that all the child components will be re-rendered, which is fine for small components but for large one’s — HELL NO.
So to remedy this we use React.memo, a function that wraps a components and is only re-rendered when it’s props change.
Example usage
Summary
So in this article, we discussed some of the concepts related to DP, saw an example, made ourselves familiar with the terminologies related to DP, and looked at DP’s relation with react.
If you have made it till here, my goal has been accomplished. Feel free to check out my other articles as well. Peace.
