Why the name "dynamic programming"?
arcanesentiment.blogspot.com
arcanesentiment.blogspot.com
Therefore, I think it's best to adhere to the rule, which is in fact generally followed by scientists, that only researchers who publish something new should propose new names.
In fact, "dynamic programming" already does already have a lot of other names. For example, certain versions of the "belief propagation" algorithm might be considered to be a form of dynamic programming, and the "belief propagation" algorithm itself has versions that are called the "forward backward algorithm" for Hidden Markov Models, the "Viterbi algorithm," the "sum-product algorithm," the "turbo-decoding" algorithm, the "Kalman filter," and the "transfer matrix." The reason there are so many names is that the "belief propagation" algorithm is a great algorithm that is often optimal, so it kept being reinvented.
It's not as bad as it seems though; an important advance that has occurred over the last decade is that researchers from very different communities have all started to describe these essentially similar algorithms using the same visual language of "graphical models." To learn more about that, see the book on "Information, Physics, and Computation," by Mezard and Montanari, the book on "Probabilistic Graphical Models," by Koller and Friedman, or my own articles ;-).
http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdf
Dynamic programming algorithms usually work from the bottom-up: you fill a table with the first stage of the algorithm, and then compute subsequent stages until you've converged on a solution. Memoization almost always works from the top-down: you start with a naive recursive algorithm, and then store function call results in a hashtable or other data structure to avoid recomputing them.
They both involve avoiding recomputation by storing intermediate results in memory. But saying that this makes them the same is sorta like saying that recursion and iteration are the same because they both use the program counter.
You can see this difference by looking at one of the ways this abstraction leaks. Consider stack traces. In a sane language, you expect an error to give you a stack trace of functions that have been called. If you treat recursion as iteration, then either you'll have to omit some function calls from the stack, or your algorithm won't work in constant space anymore. Either violates some expectations of the programmer.
I also said "recursion" and not "tail recursion". There are some algorithms that are impossible to implement without an external stack under iteration (eg. tree traversal), and others where you need to use iteration because a stack is not appropriate (eg. breadth-first search).
No they aren't. Maybe for self-recursive functions, but you're stretching it.
> The difference between tail recursion and iteration is whether or not the target of a jump happens to be the start of a function or not.
That's the difference between a subroutine and a coroutine. Yeah, having coroutines implies you have subroutines as well, but the reverse is not true.
Note: in some cases, a solution using memoization can be more efficient. See page 15 here: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
I had the opposite experience with this description. I could see that there was a table being filled in, but it didn't give me any understanding of what the table gets filled with and why. My capability with it remained cargo-cultish until I had seen memoization isolated and discussed explicitly.