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

Reply via email to