What should be the approach to solve DP problems???

I have been trying to learn Dynamic Programming for almost 2 months, but I am not getting any idea of solving DP problems. How should I start my solution? I have seen tutorials at codechef, Topcoder and many more sites but they didn’t help much…Can anyone with thorough understanding of DP, let me know how to use it. Please don’t use example like factorial and all, they are just too easy…

I had a lot of problems with DP probably because its too hard to visualize a problem correctly when someone is new to DP. The 2 things which I think helped me very much apart from a very good DP text by THOMAS H. COREMAN were :

1. Whenever a DP problem is to be solved , first you should be able to derive a recursive procedure for that. The best possible way is that instead of thinking problem for large inputs which can’t be solved by hand , one should solve the problem for inputs starting from 1 itself because once base case solution is formed , solutions for higher inputs can be solved . Now once a base case solution is known , next step is whether the solution for next higher input can be derived from this one . If not then maybe starting 2 or 3 or at most 4 base case solutions might be used for finding next higher solution . Suppose we get a solution of the form F(x)=c1 x F(x-1) + c2 x F(x-2) + c3 x F(x-3) for every x where starting 3 base case solutions are known . One can easily check whether the intutive solution formed above is correct for next 4-5 inputs . If its correct , then try to optimize the dependency on number of previous solutions for a particular x or in other sense try to remove variables from the solution once it is tested to be true for all variables. After you do this you can take an array or use Matrix exponentiation which is in most cases very good way of solving the DP problem.

2. Though the above method applies to a general way of solving DP , it always remains intutive enough unless one is too experienced with a lot of types DP problems. For this I advice you to go thru link:top coder problem archive , filter out the DP problems and start solving 500 points division 2 problems and gradually increase your level .

REMEMBER ALWAYS : INSTEAD OF THINKING ABOUT LARGE INPUTS AT FIRST, FIRST TRY TO SORT OUT A SOLUTION FOR SOME 7-8 LEAST INPUT VALUES

6 Likes

ya i agree that 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,…

2 Likes

i nearly have the same problem … i’ve read too many tutorials … i’ve understood the idea of the dp … but still i cant build the solution for a dp question… i dnt knw when to use i-1 and when to compare to the upper value in a 2 dim array … and when to see the min and etc …

me too guys…!!!