Many of the new competitive coders fear this topic DP (a.k.a. Dynamic Programming) even I spent almost 15–20 days during the start of my sophomore year to learn DP but in the end, gave up on that.
After 1 year and after solving almost 100s of DP problems from OJs like CodeForces, SPOJ and CodeChef, I devised my own way to build that recursive DP intuition which would surely help you solve multiple interview DP problems, and with a good amount of practice, you can also solve good competitive coding problems.
Let’s start from basics
DP, as mentioned on several websites like GeeksForGeeks, TutorialsPoint etc., is a way of remembering the solutions of previously solved easy sub-problems and using that past solution to solve the current problem. You can find a more precise definition of DP and its related properties here on this blog.
Solving the first DP problem
From my personal experience, I found that building a naive recursive solution followed by memoizing it is the easiest way to solve a DP problem for a beginner. Some great coders like Ashish Gupta, Ayush Ranjan, Kartik Arora use this method till date, as this method gives you a crystal clear understanding of each and every variable and parameter used in the DP function call.
Let's solve our first DP problem to get that secret of solving DP problems easily.
You have to find n’th Fibonacci Number (where 1≤n≤10⁵).
STEP 1 — Build a naive recursive solution
Note — Fibonacci series is a number theory series which begins from 0 and 1 and all the later number are the sum of previous two numbers of the series.
Disclaimer: Being programmers from now on we will begin every series and array from 0 :)
fib(0) = 0;
fib(1)=1;
From the above note, we know that the n’th term of Fibonacci series is simply
fib(n) = fib(n-1) + fib(n-2);
Recursive Code —
Time Complexity — O( 2^n ). You can read the proof here.
STEP 2— Memoize the recursive solution
Yes, you read that right its ‘Memoize’ not ‘Memorise’ ( P.S.: even I don’t know why ;) ). Here comes the most crucial part, now look which parameter is changing in each function call. Yes, you guessed it right its only ‘n’ so, we only have just one parameter to be taken care of. So if we somehow keep a record of every already computed value of n we can very easily use it to compute future results.
Let’s make a DP array of size 10⁵ and initialise all the elements to -1 (denoting we have not reached this number) to store answer for each value of n and memoize value returned from each and every function call.
Memoized Code
Time Complexity — O( N ).
So the state deciding parameter for DP array is n only.
As we move forward we will come across many problems which would have 2,3 or sometimes 4 changing parameters. So the DP states are the only thing which should be taken care of, and once you understand the changing states you will be comfortable with DP.
To check your understanding solve the same problem here without looking at the above-mentioned code snippet.
Hope it helps.
AnkitCode99 here….
