News for hackers. Stuff that matters.

A comment on Dynamic Programming for Technical Interviews. Parent comment

Re:Dynamic Programming for Technical Interviews by chillee on Friday March 15, 2019 @01:20AM (#19396810)
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.
[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by zeroonetwothree on Friday March 15, 2019 @11:36AM (#19400638)
That just has a straightforward recursive solution. I’m not even sure where the DP comes in beyond that.
[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by chillee on Friday March 15, 2019 @12:37PM (#19401310)
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 :^)
[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by bogomipz on Friday March 15, 2019 @03:50PM (#19403538)
Might you have some good resources you could share then on DP strategies and problem solving? Cheers.
[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by chillee on Friday March 15, 2019 @10:37PM (#19406069)
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!)

[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by bogomipz on Friday March 15, 2019 @10:12AM (#19399831)
Isn't that just the classic graph coloring problem though? A tree is just a type of graph.
[ Parent | on HN ]
Re:Dynamic Programming for Technical Interviews by chillee on Friday March 15, 2019 @11:04AM (#19400317)
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.
[ Parent | on HN ]