You are not logged in. Please login at www.codechef.com to post your questions!

×

Dynamic Programming resources

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.

asked 07 Dec, 00:19

shivhek25's gravatar image

4★shivhek25
364
accept rate: 0%

edited 07 Dec, 00:20


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:
1. 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...
2. 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/
3. 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...
4. 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...
http://www.spoj.pl/problems/NKLE...
http://www.spoj.pl/OI/problems/C...

link

answered 08 Dec, 10:34

codex0196's gravatar image

4★codex0196
1926
accept rate: 18%

edited 08 Dec, 10:37

CCDSAP preparation section has some really great resources to learn DP as well as other topics!

Have a look at it > LINK

link

answered 07 Dec, 00:23

ashutosh450's gravatar image

5★ashutosh450
46117
accept rate: 33%

1

Okay. Thank you

(07 Dec, 00:34) shivhek254★
link

answered 07 Dec, 00:23

taran_1407's gravatar image

5★taran_1407
2.2k622
accept rate: 23%

1

Read Competitive Programming by Steven and Felix Halim

It has a chapter on dp, which i found really useful when i started dp..

http://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp1.pdf

(07 Dec, 00:27) taran_14075★
1

Geeksforgeeks tutorial

http://www.geeksforgeeks.org/dynamic-programming/

And If you wish, Introduction to algorithms is always there at following link (though a bit advanced)

http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf

(07 Dec, 00:30) taran_14075★

Could you give me links to questions that I should start with ?

(07 Dec, 00:34) shivhek254★

In the CCDSAP preparation section, there is a curated list of questions! You can start from foundation and go to advanced with time. :)

(07 Dec, 00:46) ashutosh4505★

Practice problems: Codechef Open link and just click once on submissions to sort problems by number of successful submissions in decreasing order.

Codeforces

Spoj (I would recommend above two as above two will be in order of increasing difficulty.

link

answered 07 Dec, 00:47

taran_1407's gravatar image

5★taran_1407
2.2k622
accept rate: 23%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,321
×791
×107
×38

question asked: 07 Dec, 00:19

question was seen: 330 times

last updated: 08 Dec, 10:37