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