Lets..get started with Dynamic Programming(DP)

-


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 as well, but I found a way to tackle it, since then I have started to fall in love with DP.
I’ll share my way :-)
I’ll 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. 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 code(C++) :-
dp[0]=0;
int i=1;
while(i≤n)
{
dp[i]=a[i]+dp[i-1];
i++;
}
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 very beginner level and make you reach the advanced level :-)
Tutorial-2 is coming soon!!

Comments

Post a Comment

Popular posts from this blog

-
Image
Sphenic Number A  Sphenic Number  is a positive integer  n  which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather the first 3 digits after 1 are prime or not. Eg. 30 (sphenic number) 30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30) the set of divisor is (1,2,3,5,6,10,15,30) Examples: 30 = 2 × 3 × 5 Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather...
Read more

Fibonacci numbers with help of DP

-
Image
Well...the most and simple program which every programmer may have solved at least once.... Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.... with base condition f(0)=0  f(1)=1 In general: f(n)=f(n-1) +f(n-2) Basic Approach: A simple method that is a direct recursive implementation mathematical recurrence relation given above Here is simple CPP program.... #include<bits/stdc++.h> using namespace std;     int fib( int n) {      if (n <= 1)          return n;      return fib(n-1) + fib(n-2); }     int main () {      int n = 9;      cout << fib(n);      return 0; } That was simple....isn't it........
Read more
-
Image
Tutorial-2 is out!!!!! Fasten your seat-belt! 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:- Sum of those elements is maximum(Sum of the subset is maximum) . 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 ...
Read more