[akhilcacharya]

Formulating the recursion and caching strategy is the difficult part and it is non-trivial to identify at times.

For example, this is simple to explain in the abstract case but what about a concrete case like text justification or edit distance?

The hardest part is getting to the recurrence relation, and then implementing it.

[sanderjd]

Does the term only apply to recursive solutions? Caching is often useful in iterative solutions as well; does that count?

I would pretty much never start an interview response with a recursive solution in an interview because I pretty much never end up with a recursive solution in my work. I have very rarely been asked to do something recursively having already done it iteratively.

[akhilcacharya]

In a colloquial sense yes, DP includes both.

But to be precise, most people only consider the bottom-up approach to be actual Dynamic Programming.