I'll concede that the algorithms we get to use for this are pretty boring; pretty much Sedgewick's Algorithms-in-C level of sophistication.
Halvar Flake at Zynamics has a whole team doing genuinely interesting graph theoretic analysis of binaries, for instance to diff out otherwise-secret security flaws from Microsoft patches.
BTW, I did got bit by O(nlgn) vs O(n^2) issue, despite computers being fast nowaday. Once I used bubble sort in a cache system. It was quick and simple. Things work fine for small size cache but slowed down substantially when size > 10,000; n^2 => 100,000,000 ops. Switching to heap sort did solve the problem. So yes, understanding algorithmic complexity does help in real life work.
However, 99% of development are run of the mill coding.
(That's admittedly not a lot of DP since the days I've started to code for $$ as a student in 1994.)
I suspect that edit distance accounts for 83.52 percent of dynamic programming wordwide.
use Memoize; memoize('myfunc');
It really is not.
Memoization has the same time complexity as dynamic programming. But it has much worse space complexity.
First some approximate definitions: The tasks to which memoization and dynamic programming are typically useful are those in which a problem can be decomposed into subproblems, and subsubproblems, and so on, where problem->subproblem dependency is many-to-many, not one-to-many. That is, the dependency graph is a DAG, not a tree. By memoization I mean the process of computing the solution to a function by first looking up in a hash table to see if the solution has already been found, and only computing the solution and storing it if it has not been found. By dynamic programming I mean the bottom-up process of first solving all of the lowest level decomposed subproblems, then solving the next higher level subproblems using the solutions found at the lower level, then the next higher level using the solutions found so far, and so on up to the desired top-level problem.
Whether memoization will do the job depends on the nature of your task. In some tasks the higher-level problems depend on simultaneously knowing the answers to all of the subproblems at every level. For those kinds of problems memoization will be just fine.
But for many dynamic programming tasks, you don't need to keep around all the low-level problems: just the most immediate ones. For example, it's often the case that once you've computed problem layer N, you can get rid of all the layers 0...N-1. They're not necessary to compute problem layer N+1. For these kinds of problems the space cost of dynamic programming is just in keeping that immediate layer N. But memoization has no way of forgetting these layers, because not only is it top-down, but it's also typically depth-first. As a result, by the time you solve the final layer, you have all of the previous layers stored in your hash table.
"Coolest" algo I've ever developed would have to be parser combinators. Coolest graph algorithm: finding maximal cliques and independent sets + approximation algorithms for these.