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=dynProg And >>>> 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 >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
