Dear Furrow, Ultimately, as per your definition, is memoization a DP technique or not? I could not understand that.
Thanks in advance! Eagle On Sep 6, 2:48 am, Bartholomew Furrow <fur...@gmail.com> wrote: > > Why you said that? > > Recursion is part of dynamic programming (top down approach), am i wrong? > > This is actually a matter of definition. I'd argue that a simple recursion > like that doesn't have any of the interesting properties of dynamic > programming, but I suppose you could call it DP if you really wanted to. > Here's my definition for DP: > > - An algorithm acting on a directed, acyclic graph that is not a tree. > > You could argue away the "not a tree" part if you wanted to, in which case > calculating the factorial (and pretty nearly anything else) is indeed DP. > Here's a less controversial example of dynamic programming, used to > calculate the Fibonacci numbers: > > MEMOIZATION: > cache = [-1] * 1000 > def fib(n): > if n in (0, 1): > return 1 > if cache[n] != -1: > return cache[n] > cache[n] = fib(n-1) + fib(n-2) > return cache[n] > > RECURSION (not DP): > def fib(n): > if n in (0, 1): > return 1 > return fib(n-1) + fib(n-2) > > Notice that the only difference between the memoization and recursion > algorithms is that in the first case, we remember (memoize) the result of > function calls. What's the difference? Well, the first one is O(n), and > the second one is O(2**n). Paste those into python and see what happens > when you calculate fib(34). The first one will return almost instantly, > while the second one will take several seconds. > > "Classic" (non-memoized) DP: > fib = [-1] * 1000 > fib[0] = fib[1] = 1 > for i in range(2, 1000): > fib[i] = fib[i-1] + fib[i-2] > > This is clearly linear. It creates exactly the same array as the > memoization approach, but it's philosophically the opposite approach: it > builds up fib starting from 0, whereas memoization says "OK, what's fib(34)? > We need fib(33) and fib(32)." > > To tie this back to my original definition of dynamic programming: the > directed, acyclic graph here has nodes at each integer, and node n has edges > going to nodes n-1 and n-2. This graph is directed (the edges go one way) > and acyclic (n depends on n-1 and n-2, which don't ultimately depend on n). > > I hope this was at least a little helpful. > > Cheers, > Bartholomew --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
