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