# Dynamic programming, operational research vs competitive programming?

Dynamic programming (DP) is an important and frequent problem in competitive programming contests. Famous CLRS book categorize DP problems that have optimal substructure and overlapping sub-problems. Yet dynamic programming was invented for mathematical programming.

I believe from operational research perspective DP is more than “optimal substructure” and “overlapping sub-problems”.

So what are differences between DP in computer science and operational research?

• Can you clarify what you mean by optimal substructure and overlapping subproblems? Also, you might get different perspectives if you ask this question on cs.stackexchange.com and/or the new or.stackexchange.com. – LarrySnyder610 Jun 10 at 18:40
• @LarrySnyder610 According to the CLRS, "a problem exhibits optimal substructure if an optimal solution to the problem contains within its optimal solutions to sub-problems, and "when a recursive algorithm revisits the same problem repeatedly we say that the optimization problem has overlapping subproblems". – Jiapeng Zhang Jun 10 at 19:36

• @JiapengZhang Well, if we are using DP, then I guess we already know that the problem exhibits overlapping subproblems, but I have to confess I've never thought about it in that way before. The structures I am referring to work like this: Let $V_t(x)$ be the optimal cost in periods $t,\ldots,T$ if we begin period $t$ in state $x$. It turns out the optimal action $y$ for each $(t,x)$-pair has a special structure; it equals a constant $S_t$ if $x \le S_t$ and equals $x$ otherwise. See, e.g., profs.polymtl.ca/jerome.le-ny/teaching/DP_fall09/notes/…. – LarrySnyder610 Jun 11 at 18:18