[akhilcacharya]

Highly disagree with this. There are pretty significant approach differences between 2D DP, 1D DP, Tree DP, string operations, etc. Determining what you optimize and cache (if you do top-down, which I prefer) is often problem-specific.

The way the optimal solutions are laid out the differences between the most efficient fibonacci (O(1) space), "House Robber" independent set problem, and various problems on top of string distance seem not to have much in common between them.

[chillee]

Disagree. The general concept is the same - "Where can you collapse states into one". Someone who understands DP well should find tree DP natural, and might even come up with it themselves without learning about it beforehand. I'm not sure what you mean by string operations - most string DP problems don't require special treatment.

I agree that there are significant approach differences. However, the high level approach of: 1. Find a DP state that allows you to collapse states. 2. Find DP state transitions 3. Solve the problem

is constant among problems. The most common complaint I've heard about interview problems is that they relied on some "trick" to solve - DP problems don't have these tricks.

[bogomipz]

I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?

[chillee]

Fibonacci isn't considered Tree DP. One example of a tree DP problem is: Given a tree with N nodes, how many ways are there of coloring each node with black or white given that no two white nodes are adjacent.

[zeroonetwothree]

That just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.

[chillee]

What's your straightforward recursive solution? It might be what's considered Tree DP. If you want a harder problem I can give an example too :^)

[bogomipz]

Might you have some good resources you could share then on DP strategies and problem solving? Cheers.

[chillee]

I did make some slides here for my university's ICPC seminar: http://www.cs.cornell.edu/courses/cs5199/2019sp/

https://docs.google.com/presentation/d/1c1YUdhXOCLSVhH6Jn4TB...

It's partially targeted for competitive programming, though, so be warned that things like Tree DP/subset DP/convex hull optimization will likely not show up in interview questions (although they are pretty cool!)

[bogomipz]

Isn't that just the classic graph coloring problem though? A tree is just a type of graph.

[chillee]

Well, A. Not exactly because there's no restrictions on when you can color nodes black, and B. Graph coloring in general is NP-complete while this problem has an O(n) solution.