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.