The concept was well defined by the inventor but is now a bit vague. http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf is the best I have seen, but also check out http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html . Below are some hallmarks of DP —
* solve sub-problems before solving the bigger problem. This approach/strategy is quite general
* [M] Principle of optimality
* [C] optimal substructure
* [M] stochastic dynamic programming
* [M] tail problems
* [C] DAGs
A major category of DP problems involve decision-making at discrete-time stages. Without stochastic elements, all the “contingent” decision-making could be (brought forward and) optimized upfront with clinical precision, like a robot analyzing a maze. In that case the stages are artificial, even unnecessary.
Therefore I now feel _ u n c e r t a i n t y _ is the major differentiator among DP problems. With uncertainty at each stage, we have no choice but break up the problem into periods. Without uncertainty, we can break up the problem artificially by period, or by segment…
Therefore, here are my classification of 3 categories of common DP problems (commonly found in tutorials) —
1) with uncertainty
2) with time periods without uncertainty
3) without time period. You create artificial stages. Often the simplest DP illustrations.