2 ms·
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
by akhilcacharya 8y ago
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 8y agoDoes 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 8y agoIn a colloquial sense yes, DP includes both. But to be precise, most people only consider the bottom-up approach to be actual Dynamic Programming.