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