3 ms·
I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?
by bogomipz 8y ago
I'm familiar with 1D and 2D but what are some examples of Tree DP besides the standard Fibonacci questions?
- chillee 8y agoFibonacci 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.
- bogomipz 8y agoIsn't that just the classic graph coloring problem though? A tree is just a type of graph.
- chillee 8y agoWell, 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.
- zeroonetwothree 8y agoThat just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.
- chillee 8y agoWhat'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 8y agoMight you have some good resources you could share then on DP strategies and problem solving? Cheers.
- chillee 8y agoI did make some slides here for my university's ICPC seminar: http://www.cs.cornell.edu/courses/cs5199/2019sp/ http://www.cs.cornell.edu/courses/cs5199/2019sp/ https://docs.google.com/presentation/d/1c1YUdhXOCLSVhH6Jn4TBkca_Hgj78SpDsI-4TlgH8PY/edit?usp=sharing 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!)