DP Practice

Please suggest some problems of DP in increasing order of difficulty for the beginners.

3 Likes

DP + difficulty order
http://ahmed-aly.com/Category.jsp?ID=33

6 Likes

Hello,

Apparentely, only some problems of the above list are DP (most of them aren’t) and some links are broken…

So, here are some additional resources you can use:

DP problems with video explanations

Good luck,

Bruno

7 Likes

SUMTRIAN , this problem requires a DP-like solution, you should take a look at it;

DBOY , definitely a DP problem;

MARCHA1, one of my favorites, it can be solved with two different approaches, one of them of course is using DP and there is a tutorial there for the other solution, both of them are really interesting;

MAXCOMP, well I’m not proud of solving this one because it had a nice DP approach but I used a very naive one.

Try to solve all those problems by yourself first and then see where your solution fails and where it could be improved. At the time those are all the problems I could remember of.

2 Likes

dp is bit difficult to visualize…but i would suggest there is not much use of just reading and reading dp tutorials or going through some codes or other stuff…just start practising as much problems as possible to basically understand when should you apply it …i would suggest:

1.go throughly through the rod cutting example from cormen…and also the traditional coins exchange problem…both these problems will help you understand what actually dp is and how it can be very useful and when…:slight_smile:

2.practice as much problems as possible…here are the links to some dp based problems…
http://apps.topcoder.com/forums/;jsessionid=C684F032169B7439C8012AAB6BA2018C?module=Thread&threadID=674592
u can find more on goolge… Remember that DP is just used to reduce the repetitive work done to solve any problem by recursion…I hope now you will fell somewhat comfortable…:D,…

3 Likes

Dynamic Programming Problem :

UVA