Part of the problem of 'what is dynamic programming' is that if permit the 'states' to keep growing in 'complexity' with the stages, then nearly anything can be called dynamic programming. A big example is stochastic optimal control with an arbitrary exogenous stochastic process. In that case, at each stage, the state is just the whole past history of the process, and then for estimates of the future we take the conditional expectation given the history. So, to make stochastic optimal control, and discrete time stochastic dynamic programming, 'meaningful' we ask for a Markov assumption -- the past and future are conditionally independent given the present -- on the exogenous stochastic process.

The key, central point about dynamic programming is the computational savings we can get, when there is good news, from the basic recurrence relation. There at state i, get to do all the work using just the work did at state i + 1 for backward recurrence and state i - 1 for forward recurrence. If can't do this, and if the 'complexity' of the states keeps growing along with the stages, then are into essentially just arbitrary problems with nothing special, and little hope of gains, from dynamic programming.

How general? There is a big AI theme that the problem is solved: Just use dynamic programming! Alas, the state variables at each stage are the past history of the universe and, thus, a bit much to handle on Windows XP for now!

Again, once again, still again, for, what, a dozen times on this thread, the algorithm of the word segmentation problem is not really dynamic programming because at each stage need to use the results of the work not just at the last stage but at all the previous stages. Yes, can patch up the situation by saying that all the work of all the previous stages is now part of the current state, but if do that then the AI problem is also solved by dynamic programming because can just say that the current state has all the past history of the universe and then we don't have much for dynamic programming being anything different from everything.

For CLRS and "matrix chain multiplication", etc., to know if a solution algorithm is DP, the burden is on the proposer, not me. If someone describes the problem and writes out a clean description of why their solution is DP, then we can consider it.

But clearly what has happened is that essentially every algorithm in computer science with an outer loop from i = 1 to n is called DP, and that's not helpful.