[srean]

> And DP comes up almost never in the real world

What a big load of rubbish and gratuitous generalization !

Just because it has not come up in your work or you may have passed opportunities to recognize its applicability at your work, does not qualify you in any way to make such a broad comment.

DP has served me very well in each of the last three years in three different projects. In two of these projects I had joined the project midway. In every case the key was to recognize that DP applies where others had not and in doing so had left significant benefits on the table. In one case the 'others' was me myself. I had overlooked a potential application the first time.

So much for "almost never in the real world"

> candidates who haven't usually don't even have a chance at solving them

The claim above sounds a lot like "If all the votes were counted then candidate B would have been elected". The whole point of an election is counting the votes.

Is it such an unfair expectation that someone applying for a CS job ought to be familiar with one of its fundamental techniques ? If one is aiming for a commodity position, then perhaps yes.

[alangpierce]

It does depend on the job, and I don't doubt that there exist jobs where DP in the interview process is reasonable, especially if it's a "CS job". I'm particularly talking about software engineering interviews, to be clear, not research positions or anything like that. Even in software engineering, I could imagine DP being important if the product relies heavily on high-quality string diffing, for example. I'm certainly interested to hear your real-world applications if you're able to share. I guess I have seen memoized DAG traversal come up, so in that sense I've seen DP, but it's not quite the same as "take this non-recursive-looking problem and make it recursive so you can memoize".

Two situations come to mind when I think about DP being used in real-world applications (both just things I heard about): a talk I heard about how Google News compares news pages before and after the publisher makes an HTML change, and DNA sequence alignment problem. Both of them went like this:

1.) We want to find a perfect solution, but the search space is exponential size.

2.) Hey look, by using dynamic programming we can reduce the complexity to n^2 time and space.

3.) Wait, n^2 time/space is still too inefficient for many real-world use cases. Rather than trying to find a perfect solution, let's settle for a good enough solution by rethinking the approach and applying some heuristics. By putting some clever thought into it and sacrificing a little bit of quality, we can get something that takes O(n) time in practice.

So I think an initial goal of looking through an exponential search space for an optimal solution (often what DP is solving) is often misguided anyway, since often "optimal" isn't actually so important.

[srean]

Appreciate this more nuanced take. I think 'software engineering" job and "CS job" arent quite complementary. I do disagree that 'optimal' is often unimportant. It does matters a great deal when it matters, especially if that is the core of the project.

Dont know how much I can talk about the problems. One of them was definitely a string related problem but not about string diffing. The other two were on optimizing cost over all possible partitioning of a set (different kinds of sets in the different projects) -- hence my embarrassment at not having noted the same structure in the two different problems right away. It was one of those moments, "Wait a minute. I am doing this wrong. The sets are different but in an abstract sense I am doing the same thing in the other project over a different set".

Without DP it would have been very hard to come close to the optimal solution by local explorations unless one got lucky and started of by looking around a promising place in the search space.

I am sure DP can be put to some use when trying to optimize the placing of VMs on hosts. If done well the savings in dollars can easily hit 6 figures or more. These are real problems with real money at stake.