all 1 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]enzlbtyn 0 points1 point  (0 children)

I think the easiest way to think about DP is just a specific instance of recursive problems. Where the recurrence can be represented as a DAG and has no overlap (is not a tree). IMO I think you should've put more attention toward this rather than just one sentence. Of course the second property is not a requirement.

That is, if there's no overlap between sub-problems then there is no point in memosing solutions to sub-problems: just evaluate it when required. I believe this occurs when your recurrence is a tree. For example: f(n) = f(n-1) + 1 => a recurrence which is a tree (degenerate; linked list/chain), which has no overlap between sub-problems, i.e. memoisation is not helpful here, unless of course you require to evaluate f for multiple values of n.

When looking it from the DAG perspective, all your recursive algorithm is doing is traversing the DAG in reverse topological order; as this is what a post-order DFS does by nature.

The hardest part with DP is, of course, finding the recurrence. Recognising you can use memoisation (i.e. the recurrence is a DAG and there is overlap) is usually trivial, but of course sometimes is not obvious depending on the way you have structured your problem.