You may wanna try the Problem in Todays TopCoder SRM , http://www.topcoder.com/stat?c=problem_statement&pm=10620
<http://www.topcoder.com/stat?c=problem_statement&pm=10620>Its a good problem. Give it a try :) ,, Don't worry, we are there to explain in case. - Anil Kishore, IIIT-Hyderabad. On Thu, Sep 10, 2009 at 6:52 PM, samuel jawahar <[email protected]>wrote: > Dynamic programing gives the effective way of recursion, with table that > contains the previous results > Regards > Jawahar > > > On Thu, Sep 10, 2009 at 5:55 PM, amit jain <[email protected]> wrote: > >> thanx buddy.... >> >> On Thu, Sep 10, 2009 at 2:11 PM, Mayank Jaiswal <[email protected]>wrote: >> >>> Hi amit, >>> >>> I'll try to help you. >>> Recall the definition of dynamic programming. >>> *Dynamic programming is a method of solving complex problems by breaking >>> them down into simpler steps. >>> * >>> So, when solving a problem, think that whether you are solving same >>> subproblem again and again or not. If yes, just find out a way in which you >>> can store the result of smaller problems and use it further in the algorithm >>> . >>> >>> By the term *optimal substructure*, we just mean that when you realise >>> your bigger problem to be consisted of similar smaller subproblems, the >>> solution to this subproblem will contribute to optimal solution of parent >>> bigger problem...... it sounds confusing and complex ...i know. Just forget >>> this. Practice a few problems .... Cormen (Introduction to algorithms) is a >>> good book to learn. >>> >>> >>> Solving some problems will automatically give you a feel of what to do >>> .... its not a big deal as it sounds to be. Best of luck! >>> >>> Cheers, >>> Mayank >>> >>> >>> >>> >>> >>> On Thu, Sep 10, 2009 at 1:55 PM, Anil Kishore <[email protected]>wrote: >>> >>>> >>>> If you think of it as some standard step-by-step thinking, then it may >>>> not work most of the time. By more practice, you will develop the art >>>> of DPing ;) . . . Its all about, 'remember your past to your memory >>>> capacity' >>>> >>>> May be its something like this. , >>>> -> Hmm the Problem looks good , lemme imagine as a big picture >>>> -> I see, we need to solve this way (think as if you are explaining the >>>> answer to your friend) >>>> -> Oh, I am doing the same kind of things and need to solve similar >>>> sub-problems >>>> -> Aha!, its recursion . . I knew it ! , lemme write the function >>>> corresponding to the recurrence relation >>>> -> oh .. wait, am I calling the function more than once, with same >>>> parameters.. yaya, lemme memoize >>>> -> Aaah!, i figured out the order in which the subproblems are solved . >>>> . >>>> -> Aha !, its DP . . I knew it ! :p >>>> >>>> If you are in doubt, you can simply memoize (even if its not needed). >>>> May be someone who can solve advanced DP in less time, can explain >>>> better. >>>> >>>> - Anil Kishore >>>> >>>> >>>> On Thu, Sep 10, 2009 at 1:41 PM, amit jain <[email protected]> wrote: >>>> >>>>> okk >>>>> how do you think optimal substructure step ? >>>>> On Thu, Sep 10, 2009 at 1:34 PM, Hawston LLH <[email protected]>wrote: >>>>> >>>>>> i guess only practice more and get more familiar with it is the only >>>>>> useful trick if there is any. :) >>>>>> >>>>>> On Thu, Sep 10, 2009 at 3:57 PM, amit jain <[email protected]>wrote: >>>>>> >>>>>>> u know we have not enough time during competition and sol of dp looks >>>>>>> like they will take 1 complete day.. >>>>>>> now a days i m spending my whole day to solve a single dp problem >>>>>>> like we had in qualification round. >>>>>>> and i read out both clrs and as well as topcoder link >>>>>>> so plz suggest me useful trick to solve them... >>>>>>> thanks in advance.. >>>>>>> On Wed, Sep 9, 2009 at 11:10 PM, Kaushalya Madhawa < >>>>>>> [email protected]> wrote: >>>>>>> >>>>>>>> This is good! >>>>>>>> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProgAnd >>>>>>>> refering CLRS will be helpful >>>>>>>> Regards, >>>>>>>> Kaushalya Madhawa >>>>>>>> http://kaumad.wordpress.com >>>>>>>> http://most-wanted-stuff.blogspot.com >>>>>>>> >>>>>>>> twitter: http://twitter.com/kau_mad >>>>>>>> skype: kau.mad >>>>>>>> gtalk: kau.mad >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On Wed, Sep 9, 2009 at 3:27 PM, Sagar Shah >>>>>>>> <[email protected]>wrote: >>>>>>>> >>>>>>>>> Can anyone please suggest me some good tutorial/book to learn >>>>>>>>> Dynamic Programming? >>>>>>>>> >>>>>>>>> Thanks >>>>>>>>> Sagar Shah >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> -- >>> Mayank Jaiswal >>> B.Tech >>> Final Year Student >>> Computer Science and Engineering >>> Indian Institute of Technology, Kharagpur >>> >>> D-220, Nehru Hall of Residence >>> +91 97344 28874 >>> http://www.linkedin.com/in/msjaiswal >>> >>> >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
