[chillee]

I actually disagree. Of the problems that are commonly asked in programming interviews, DP is perhaps the one that tests "general problem solving" the best.

Many other problems require problem-specific tricks/uncommon tricks. On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

[mayank]

> On the other hand, there's rarely a DP problem (that comes up in interviews) that relies on a problem-specific trick.

That's a pretty big parenthetical. DP problems as a class are full of clever tricks for elegant solutions that took decades of research. Any practical use of DP is almost certainly going to use problem-specific tricks as well. Which makes DP tricky, especially in interviews.

[chillee]

Yes, there's a ton of DP problems that require clever tricks. I've had to show these tricks to friends who believed that DP problems were too formulaic.

Could you give an example of DP problems that show up in interviews that require problem-specific tricks? I'm contrasting DP problems with other interview questions like: Find whether a linked list has a cycle in O(1) memory or implement a queue with 2 stacks.

[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.

[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.