Could someone please provide some resources that will help me learn DP right from the basics ? I have gone through a few links and I know the theory part but they were of no help when I started implementing them. So, links to some starter-pack programs would be appreciated. Thank you in advance.
1 Like
CCDSAP preparation section has some really great resources to learn DP as well as other topics!
Have a look at it > LINK
1 Like
Refer this
PS:I’m adding more…
1 Like
Practice problems: Codechef Open link and just click once on submissions to sort problems by number of successful submissions in decreasing order.
Spoj (I would recommend above two as above two will be in order of increasing difficulty.
1 Like
TopCoder Dynamic Programming - From Novice to Advanced explains DP by solving questions.
Dynamic Programming | Set 1 GeeksforGeeks explains different types of dynamic programming, start by doing set 1.
DP is not an algorithm its a technique of solving problems and that’s why they require practice. Just keep practicing and you will start solving problems on your own in no time.
Read the Dynamic programming chapter from Introduction to Algorithms by Cormen and others. You have to understand the theory of dividing a problem into subproblems, storing the intermediate results in the array and see how are some standard problems solved with DP.
There are more types of dynamic programming problems. Here are the most famous ones, sorted increasing by their difficulty:
- Problems which simply ask you to come up with the formula of calculating the answer from the subproblems. These are the most common ones and probably the ones you want to practice on (95+% of DP problems are of this type). On TopCoder, they are usually ranked as Div1-500 and easier. On other online judges just look for the problems with many successful solutions.
The number of dimensions of the array doesn’t really tell much about the problem difficulty, so don’t judge based on that. It only needs a little more implementation.
The hardest problems in this category require you to use bitmasks. For example:
http://community.topcoder.com/st…
Here is a very nice tutorial on bit manipulation techniques:
http://community.topcoder.com/tc…
- Problems which require you to come up with efficient linear recurrence, putting the recurrence into the matrix and calculate the N-th power of the matrix. Examples are:
http://www.spoj.pl/problems/XORR…
http://www.spoj.pl/problems/TRKN…
http://www.spoj.pl/problems/RP/
- Problems which require you to eliminate the inner cycle in the algorithm. For more information you can look at Knuth’s speedup of calculating the optimal binary search tree
http://dl.acm.org/citation.cfm?i…
or
http://community.topcoder.com/tc…
- Problems which require you to effectively calculate and operate on the convex hull of the optimal solutions. For a nice problem with a solution, look at the problem Harbingers from CEOI 2009. Other examples are:
http://www.spoj.pl/problems/MKPA…
3 Likes
Read Competitive Programming by Steven and Felix Halim
It has a chapter on dp, which i found really useful when i started dp…
1 Like
Geeksforgeeks tutorial
And If you wish, Introduction to algorithms is always there at following link (though a bit advanced)
1 Like
Okay. Thank you
1 Like
Could you give me links to questions that I should start with ?
In the CCDSAP preparation section, there is a curated list of questions! You can start from foundation and go to advanced with time. 
I am a NITian got placed at Flipkart (with a package around 30lpa i wish i could disclose it). I have encoded my years of experience of coding into a playlist of Dynamic Programming where I have explained well how to identify whether its a DP problem and how to approach it.
Moreover I have grouped similar variations of a standard problem together to let the students grasp the concepts well.
Take a look: Dynamic Programming | Coding | Interview Questions - YouTube (Dynamic Programming Playlist | Coding | Interview Questions | Tutorials | Algorithm - YouTube)
There are 10 standard problems of DP, doing them good you can almost solve 80 problems, which are just the variation of those 10 standard ones.
8 Likes
start with basic knapsack problems like subset sum, maximum profit , fractional knapsack etc