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