Master dynamic programming with the best free tutorials on internet for coding interviews and competitive programming !

Ask a question:

PART-1 : 

So, most of us have heard about this term “DP” a lot and have seen people in fear as soon as they listen to it.

I used to fear DP a lot too , but then I found the easiest way to master it :-) 

I will share my way :-) 

I will make you fall in love with this topic . 

Important points:-

1. To be good at DP, all you have to do is solve classical DP-problems and their variations.

2. Recognize patterns and improve upon your thinking skills in DP

3. Love DP, it will love you back !

There are many variations of DP and I’ll discuss them all one by one so you can become a pro!

Introduction to DP:-

To find solution to a problem, we divide the problem into sub-problems, find answers to those sub-problems , combine them to get the original answer!

That’s it!

Example:- Say I ask you to calculate :- (1+2+3+4+5) You do this:-   

  1. Break it into sub-problems : (1+2) + (3+4) +(5)
  2. 2. Find answers to those sub-problems: (3) + (7) + (5) 3. Combine them to get the answer to the original problem : 15 :-)

That’s what we call dynamic programming ! :-)

My personal trick :-

dp[i] usually mean the best answer to the problem till the i’th index of the array.

Obviously, final answer will be dp[n](where ’n’ is the size of the array)

We cannot calculate dp[n] directly, we first need to calculate dp[1],dp[2],… and combine their results to find the value of dp[n] :-)

Problem-1 : We are given an array of integers(a[n]) . We are given multiple queries of the form : (1, i) which means we need to output the sum of all numbers from index- ‘1’ to index ‘i’ of the array.

Analysis : Running a loop for each query and finding the sum is a good idea but not very efficient as it takes O(N*Q) time.

Lets create a dp-array of size ‘n’.

dp[1]=sum of all numbers from (1,1)

dp[2]=sum of all numbers from (1,2)…

and so on.

Say, a[5]={4,5,3,2,1}…(assume 1-based-indexing here) So, dp[1]=4(pretty easy)…..(1)

dp[2]=4+5=9………(2)

dp[3]=4+5+3=12…..(3) and so on.

So, for any index ‘i’ ,

dp[i]=a[i]+dp[i-1],

Example:-

dp[3] = a[3] + dp[3–1] = a[3] + dp[2]= 3 + 9 =12 ….(which is same as equation…(3))

Piece of pseudo-code :- 

dp[0]=0;
 int i=1;

 
 while(i≤n) 

{
dp[i]=a[i]+dp[i-1]; 

i++;
 } 

print(dp[n])



This took O(N) time!

Voila! We did it!

So, now for all the queries, all we gotta do is output the value of dp[i], which we have already pre-computed :-)

Time taken:- O(N+Q) [ O(N) for pre-computation, as we answered each query in O(1), total time taken was O(Q) ]

So you get the basic idea of DP is to make a recurrence relation ,and then run a loop ,and calculate(pre-compute) the values :-)

My aim is to start this series from a very beginner level and make you reach the advanced level :-)



Part-2 : 

Problem-2:- Understanding this problem and its solution properly will make a strong foundation for you in the DP world! (This worked for me :-) )

Here we go :   Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:-

1. Sum of those elements is maximum(Sum of the subset is maximum) .

2. No 2 elements in the subset should be consecutive.

Example :- {2,4,6,7,8}

Answer:- {2+6+8=16}

Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array.

For the above example,

dp[1] = 2 (2), [This is the best answer you could get if size of the array was one]

dp[2]= 4(4),[This is the best answer you could get if size of the array was two]

dp[3]=8(6+2),[This is the best answer you could get if size of the array was three]………lets call this equation-(1)…

dp[4]=11(7+4),[This is the best answer you could get if size of the array was four]

dp[5]=16(2+6+8),[[This is the best answer you could get if size of the array was five]

Now , the next thing that I am going to say, you gotta feel it deeply . If you are able to do it, you win!!

Say, I have calculated dp[1],dp[2] and dp[3] by pure observation. Now, I have to calculate dp[4].

So I have only 2 choices:-

i)Include the 4'th element , if I do this, I can’t include the 3rd element as consecutive elements are not allowed, so ,

dp[4]= a[4]+dp[2]…..(answer will be 4th element plus the best answer till index ‘2’ of the array)

ii)Exclude the 4th element, we don’t select it! So the previous answer is the current answer, we don’t change anything,

dp[4]=dp[3],

Final answer is the maximum of two choices :-> dp[4]=maximum(a[4]+dp[2],dp[3])

=maximum(7+4,8)

=maximum(11,8)

=11…..(verify this with equation…(1))

Voila, we did it !!!

So,the recurrence relation for this problem is, for any ‘i’ ,

dp[i]=max(a[i]+dp[i-2],dp[i-1])

We will calculate dp[i] for all ‘i’ from (1 to n) using the above formula.

And dp[n] will be the maximum possible sum for the whole array!!

Woohoo!!!!

Some code:-


dp[0] = 0;

dp[1] = max(a[1],dp[0]);

i = 2;

while(i≤n)

{

dp[i] = max(dp[i-2]+a[i], dp[i-1]); i++;

}



Part-3 : 

Aim of this series:- “ To make you fall in love with Dynamic Programming. To show you the actual beauty of this topic. To go from beginner level to master level.”

Some of the common tricks we have learned as of now :

1. Usually, we create a dp-array , and dp[i] means the maximum sum(best-answer) we could get till index-’i’ of the array.

2. We need to find a recurrence relation, in simple words, we need to create a formula for dp[i] in terms of

dp[i-1],dp[i-2],….etc…

3. We run a for loop, which calculates dp[1],dp[2]…..and finally dp[n].

4. dp[n] means the answer for the whole array.

Last time, we discussed this problem

:-

Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:-

1. Sum of those elements is maximum(Sum of the subset is maximum) .

2. No 2 elements in the subset should be consecutive.

Example :- {2,4,6,7,8}

Answer:- {2+6+8=16}

Now, lets solve a harder variation of this problem,which will make our understanding strong.

Modified Version : We are given ‘2’ arrays . Select some elements from both of these arrays (select a subset) such that:-

1. Sum of those elements is maximum(Sum of the subset is maximum).

2. No 2 elements in the subset should be

consecutive.(Note:-If you select, say 5'th element from Array-1, then you are not allowed to select 4'th element from either Array-1 or Array-2 :-) )

Example:-

Array 1(a1) : {1,5,3,21234}

Array 2(a2) : {-4509,200,3,40}

Answer:- (200+21234=21434)

Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array.

For the above example,

dp[1] = 1(1) , [This is the best answer you could get if size of the array was one]

dp[2]= 200(200),[This is the best answer you could get if size of the array was two]

dp[3]=200(200), [This is the best answer you could get if size of the array was three]………lets call this equation-(1)…

dp[4]=21434(200+21234), [This is the best answer you could get if size of the array was four]

Say, I have calculated dp[1] , dp[2] and dp[3] by pure observation. Now, I have to calculate dp[4].

So I have only 2 choices:-

i)Include the 4'th element (of either array-1 or array-2, if I do this, I can’t include the 3rd element(from both the arrays) as consecutive elements are not allowed, so,

dp[4]= (max(a1[4],a2[4])) + dp[2])…..(answer will be 4th element plus the best answer till index ‘2’ of the arrays)

ii)Exclude the 4th element, we don’t select it! So the previous answer is the current answer, we don’t change anything,

dp[4]=dp[3],

Final answer is the maximum of two choices :-> dp[4]=maximum(max(a1[4],a2[4])+dp[2],dp[3]) =maximum(max(40,21234)+200,200)

=maximum(21234+200,200)

=maximum(21434,200)

=21434…..(verify this with equation…(1))

Voila, we did it !!!

So,the recurrence relation for this problem is, for any ‘i’ ,

dp[i]=max( max(a1[i],a2[i]) +dp[i-2],dp[i-1]) 

Some C++ code:-


//dp[1] and dp[2] is calculated by observation. //we run a loop from i=3 to i=n , dp[n] is the final answer. i=3;

while(i≤n)

{

dp[i]=max( max(a1[i],a2[i])+dp[i-2],dp[i-1]); i++;

}

cout<<dp[n];



Part-4 : 

What have we learned so far?

1)We always create a dp-array of size ’n’.

2) dp[i] is the best answer for the given problem till index ‘i’ of the array.

3)dp[n] is the final answer!!!

4)We write the values of dp[1],dp[2] by pure observation.(as its very easy to do!!)

5)We find a formula, example formula : dp[i]= 2*dp[i-1]+3*dp[i-2] , and apply this formula (run a for loop) to calculate dp[3],dp[4],….dp[n]…And then we are done!!

So let’s discuss a delicious problem today! We are given a number ‘x’, we want to reduce it to ‘1’ in minimum number of steps possible!!

At each step, we are allowed to :

1)Decrement the given number by ‘1’……..(i)

2)Decrement the given number by ‘2’ ………..(ii)

3)Divide the given number by ‘7’ only if it is divisible by ‘7’……..(iii)

So how do we solve this problem(find the minimum number of steps to reduce any given ‘x’ to ‘1’) ?

We chill and feel good about the precious life given to us by God, now we go back to the problem!

Check out the steps I taught above!!!

1)First we create a dp-array of size ‘x’.

2)dp[i] is the best answer for any number ‘i’.In other words, dp[i]=minimum number of steps required to convert the number ‘i’ to 1.

3)We will find dp[1],dp[2],dp[3],dp[4],……..dp[x].

4)dp[x] is the final answer!!!!

So, tell me, what is the value of dp[1]???

How many steps does it take to reduce ‘1’ to ‘1’???? Answer : Zero.

Hence, dp[1]=0

Now, tell me, how many steps does it take to reduce ‘2’ to ‘1’???

Answer: It’s simple, 1 step is what it takes .(Just decrement 1 from ‘2’….refer(i) above!!)

Therefore,dp[2]=1.

Now, dp[3]?? 1st way : 3 — ->2 — 

->1(Total-2-steps-taken!!)

2nd way : 3 — ->1(Only 1 step taken).

Hence dp[3]=minimum(1-step,2-steps)=1-step. Now,dp[4]??

1st way : 4 1.(Decrement by 2, then decrement by 1) 2nd way : 4 2 — ->1(Decrement by “1” 3 times)

3rd way : 4 3 — ->1(Decrement by 1, then decrement by 2)

Hence , dp[4]=2(2 steps).

Now, for dp[5], let’s use some other trick!!

We already know that 5 can be reduced to ‘3’ or ‘4’ in the first step(DECREMENT EITHER BY ‘1’ OR ‘2’).

Say, we reduce it to “3”. Now, we already know the best answer for “3”, which is dp[3]!!! Now ,the other choice is to reduce it to “4” in the first step itself. We already know the best answer for “4”, which is dp[4]!!! Eurekaa!!! Eureka!!! Eureka!!!

Hence, dp[5]=1+dp[3] ….(Why +1 ?? Because it took “1” step to convert five to three) OR dp[5]=1+dp[4] , Henceforth,

dp[5]=minimum(dp[4]+1,dp[3]+1)=

minimum(2+1,1+1)=minimum(3,2)=2!!!

So the formula is, dp[i]=minimum(dp[i-1]+1,dp[i-2]+1).

Lets now calculate , dp[14] for example .

dp[14]=minimum(dp[13]+1,dp[12]+1)….. BUT ARE we forgetting something???

Yes!!! “14” is divisible by “7”,

so we can apply the third operation, as well, we may divide it by “7” 14 14/7 — ->2 — ->1(Took only-2-steps!)

Hence, dp[14]= dp[14/7]+1 is one of the choices,

So the final formula for any number divisible by “7” is : dp[i]=minimum(dp[i-1]+1,dp[i-2]+1,dp[i/7]+ 1)…

See, dp is so lovely, I love it more than my girlfriend You should too :P

Some pseudo code:-

dp[1]=0;

dp[2]=1;

dp[3]=1;

dp[4]=2;

i=5;

while(i≤x)

{

if(i%7==0)

{

dp[i]=min(dp[i/7]+1,dp[i-1]+1,dp[i-2]+1); }

else

{

dp[i]=min(1+dp[i-1],1+dp[i-2]) ;

}

i++;

}

Related-problems:-

1)https://www.geeksforgeeks.org/reduce-a-number-to-1 -by-performing-given-operations/

2)https://www.geeksforgeeks.org/minimum-number-of operations-required-to-reduce-n-to-1/

3)https://www.geeksforgeeks.org/minimum-steps-minimize-n-per-given-condition/


Part-5 :

The principal on which Dynamic Programming operates :- “We always find the most optimal aka the best solution using dynamic programming.”

Make sure you read all the previous tutorials before you begin to binge learn this one.

We solved this problem in Tutorial-2 :

Given an array of integers(positive as well as negative) , select some elements from this array(select a subset) such that:-

1. Sum of those elements is maximum(Sum of the subset is maximum) .

2. No 2 elements in the subset should be consecutive. Example :- {2,4,6,7,8}

Answer:- {2+6+8=16}.

Let’s change the second condition :-> Instead of 2, No 3 elements in the subset should be consecutive.

Now, what do we do ?

I taught you few tricks earlier and they are as follows:-

1. Usually, we create a array , and dp[i] means the maximum sum(best-answer) we could get till index-’i’ of the array.

2. We need to find a recurrence relation, in simple words, we need to create a formula for dp[i] in terms of dp[i-1],dp[i-2],….etc…

3. We run a for loop, which calculates dp[1],dp[2]…..and finally dp[n].

4. dp[n] means the answer for the whole array.

Example Array : {3000,2000,1000,3,11}

Answer:- {3000,2000,3,11}=sum()=5014.

(No-3 elements in the selected subset are consecutive) Now,example Array:- {a[1],a[2],…………a[N]}

Say, we calculated dp[1],dp[2],dp[3],dp[4],… by pure observation by our eyes ❤

Now, let’s say, we have to calculate dp[i] for any index- ‘i’ , how do I do that ?

Our choices :-

1. Don’t include a[i] . It means we do nothing . The previous answer is considered as the best answer. Hence,

dp[i]=dp[i-1].

2. Include a[i]. Imagine this:{a[i-3],a[i-2],a[i-1],a[i]….}.We know that ……..a[i-2],a[i-1] and a[i] are not allowed to be consecutive.So if we select a[i], then the next element we gotta select is a[i-2](dp[i-2]), not …………..a[i-1].Hence..

dp[i]=a[i]+dp[i-2](dp[i-2] →best answer till index …‘i-2’ of the array)

3. Include a[i].Imagine this:{a[i-3],a[i-2],a[i-1],a[i]….}.We know that ……..a[i-2],a[i-1] and a[i] are not allowed to be consecutive.So if we select a[i], then if we select a[i-1],we are not allowed to select …………..a[i-2]. We will

select…a[i-3](dp[i-3])…..Hence..

….dp[i]=a[i]+a[i-1]+dp[i-3](dp[i-3] →best answer till index …‘i-3’ of the array)

Maximum of the above three choices will be the answer for “dp[i]” Voila!We did it!

We found the recurrence relation :-

dp[i]=Maximum(dp[i-1],a[i]+dp[i-2],a[i]+a[i-1]+dp[i-3])

Run a for loop and calculate dp[i] for all “i” from 4 to N. dp[N] will be the final answer :-)

Some C++ pseudo-code:-

//calculate dp[1],dp[2],dp[3]…..by observation!! i=4;

while(i≤N)

{

dp[i]=Maximum(dp[i-1],a[i]+dp[i-2],a[i]+a[i-1]+dp[i-3]); i++;

}

cout<<dp[N];

Problem-2:

We start at index- ‘1’ of the array and strictly end our journey at index- ’N’ . We can make jumps of length “1” or “2” . We have to find a journey with maximum sum.

Example Array :-

{1,-1,100,-11,200,300}

Our Optimal(Best) Journey :- 1 — ->(jump of length-2)100 — ->(jump of length-2)200 →(jump of length-1)300

Hence, Maximum Sum=1+100+200+300=601.

I taught you few tricks earlier and they are as follows:-

1. Usually, we create a dp-array , and dp[i] means the maximum sum(best-answer) we could get till index-’i’ of the array.

2. We need to find a recurrence relation, in simple words, we need to create a formula for dp[i] in terms of

dp[i-1],dp[i-2],….etc…

3. We run a for loop, which calculates dp[1],dp[2]…..and finally dp[n].

4. dp[n] means the answer for the whole array.

Given Example Array:- [1,-1,2,4,3,-5,6,7,8,-80]

dp[i]=Best answer I can get till index- ‘i’ if I include a[i]. dp[1]=1.

dp[2]=1+(-1)=0

dp[3]=1+2=3(Best answer I can get till index- ‘3’ if I include a[3],where a[3]=2).

How do, we calculate dp[4] , now ??

Think…Think….Think!!!!

We know that we have to include a[4], as per the definition of dp[i].

Hence, dp[4]=a[4]+ ?

We can make jumps of length- “1” OR “2”, so we can reach index- ‘4’ from index- ‘3’(3 — ->4) or index- ‘2’(2 — ->4)

Hence,

dp[4]=a[4]+dp[3]

OR

dp[4]=a[4]+dp[2]

Maximum of both is our answer :-)

Hence, dp[4]=Maximum(a[4]+dp[3],a[4]+dp[2])

The recurrence relation is:

dp[i]=Maximum(a[i]+dp[i-1],a[i]+dp[i-2]) Run a for loop and calculate dp[i] for all “i” from 4 to N. dp[N] will be the final answer :-)

Some C++ pseudo-code:-

//calculate dp[1],dp[2],dp[3]…..by observation!! i=4;

while(i≤N)

{ dp[i]=Maximum(a[i]+dp[i-1],a[i]+dp[i-2]);

i++;

}

cout<<dp[N];

Problem-3:

We start at index- ‘1’ of the array and strictly end our journey at index- ’N’ .We can make jumps of length “1” or “2” or “3” or….till “K” . We have to find a journey with maximum sum.

Its same as the problem-2 only difference is that we can make jumps of all lengths from “1……TO…..K” ,

So,our new recurrence relation will be : — 

dp[i]=Maximum(a[i]+dp[i-1],a[i]+dp[i-2],a[i]+dp[i-3]+………a[i] +dp[i-4]+………+a[i]+dp[i-K])

Run 2 for loops and calculate dp[i] for all “i” till N. dp[N] will be the final answer :-)

Code:-

//dp[1],dp[2],dp[3]…calculate on your own by observation!! i=4;

while(i≤N)

{

//dp[i]=Maximum(a[i]+dp[i-1],a[i]+dp[i-2],a[i]+…….);

j=i-1;

g=1;

c=-1000000000000;//just declaring a very small possible number..

while(j≥1 && g≤k)

{

x=a[i]+dp[i-g];//comparing all of them…..

if(x>c)

{

c=x;

}

g++;

j- -;

}

dp[i]=c;

i++;

}

cout<<dp[N];

One of the problems that will be discussed in future is:-

Same as problem-2, how many journeys are possible which will give an even sum or maybe odd sum ;) ? :-)


 



Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .