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