Why you said that? Recursion is part of dynamic programming (top down approach), am i wrong?
On Sat, Sep 5, 2009 at 6:13 PM, itissid<[email protected]> wrote: > > Dude that factorial example is not DP!!! > > On Sep 5, 12:43 am, Hawston LLH <[email protected]> wrote: >> maybe you can read more on dynamic programming first, it is about how to >> divide the problem into smaller piece of elements recursively. >> >> simple example - write a factorial function N! >> >> int factorial(int N) >> { >> //bounday or stopping condition >> if (N<=1) >> return 1; >> >> //here, try to process 1 step explicitly, and leave the >> //remaining jobs to the recursive function >> return N * factorial(N-1); >> >> } >> >> as you can see, to formulate a recursive function or algorithm, you need to >> know what can be done "repeatedly" or recursively. >> >> In graph problem, sometimes the decision cannot determine on the cell >> itself, it relies on neighbours. >> But the decision of neighbours also relies on their neighbours.. there is a >> repeat pattern, thus in general, you can write something like this: >> >> //pseudo code >> void DoSomething(graph g, position p) >> { >> //similarly, you have boundary or stopping condition >> if (stopping condition satisfied) >> return; >> >> //try to process 1 step and leave the remaining jobs to >> //the recursive function >> for (n = neighbour of p in g) >> { >> //do something >> ............. >> >> //pass on to recursive function to solve remaining >> DoSomething(g, n); >> >> } >> } >> >> So, you need to analyse the question and determine the part of recursion, >> then implement the code. That is the very first step. After you know the >> technique, then try to learn how to optimise the algorithm, since you can >> solve the question using different ways of recursion, together with suitable >> data structure and use of memory. >> >> On Sat, Sep 5, 2009 at 2:59 PM, CodeJunky <[email protected]>wrote: >> >> >> >> > thanks buddy!!!!!! >> > im actually new in coding arena ..........well i understood the >> > problem and sawmany implementations >> > the thing is i have read quite a few graph algorithms but im unable to >> > implement them in any problem >> > since i donot have any other mentor or tutor ..........forums are the >> > only source of learning >> > I went through the top coder tutuorial of graph but i could not >> > understand the problems discussed >> > can anyone give me links to some straightforward problems so that >> > gradually i reach a level where >> > i can comprehend and code any graph problem >> >> > thanks and regards!!! >> >> > On Sep 5, 10:24 am, Hawston LLH <[email protected]> wrote: >> > > 1. start from top to bottom, left to right, check each cell one by one. >> > If >> > > current location is already labelled, then label the locations stored >> > > previously in the path with that label. Then clear the path vector and >> > > continue step 1. >> > > 2. otherwise, check north, west, east, south neighbour and get the >> > minimum >> > > location (x_min, y_min) >> > > 3a. if min location is different from current location, then push/store >> > > current location into the path vector and proceed to step 1 with the min >> > > location. >> > > 3b. otherwise, meaning current location is a sink, label it with next >> > > char C' and also label all locations stored previously in the path vector >> > > with C'. >> >> > > On Fri, Sep 4, 2009 at 7:37 PM, CodeJunky <[email protected] >> > >wrote: >> >> > > > Can anyone please explain me the water shed problem and the graph >> > > > approach > > > > -- M@ http://matteolandi.altervista.org/ --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
