[Cyph0n]

Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down.

For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1).

With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10).

Following on from this, you usually build up the solution in an array, sequentially, instead of navigating down the tree of solutions and storing as you go (memoization).

[alangpierce]

I've done a lot of programming contest stuff, and at least when speaking casually, I've always heard DP as referring to either the top-down approach or the bottom-up approach. They have their tradeoffs (though usually top-down is better because it's easier to implement), but they're both DP. It may be that you're technically not supposed to use the term "DP" for the top-down variant, but in practice people use the term to refer to both.

[chillee]

I'd say that in competitive programming, bottom-up is actually preferred.

Bottom up is faster, usually shorter to code, and allows certain kinds of optimizations you can't do with top down (sliding window, convex hull trick, etc).

Top down frees you from needing to think about order of computation, and also allows a different set of optimizations from bottom up (divide & conquer).

[alangpierce]

TBH it's been a while since I've done these contests seriously, but I remember the "order of computation" problem to be hard to think about for less trivial cases (like with a 3-dimensional table). But maybe I worried about it too much.

And just for fun, while we're listing these things:

Another advantage to bottom-up that I've seen is that sometimes top-down causes your recursion to get so deep that you run out of space in your call stack. Another advantage to top-down is that you're only filling in the subset of the table that's needed for the specific problem you're solving. Certainly someone with a lot of experience should be able to do both.

[chillee]

Some examples where order of computation isn't that trivial is when you're doing DP on trees or a DAG.

+1 to the "filling in a subset" part. Usually it's not too relevant because it's merely a constant factor change, but occasionally it'll be very important.