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?

  • 1
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 Jun 10 at 18:40
  • $\begingroup$ @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". $\endgroup$ – Jiapeng Zhang Jun 10 at 19:36

As an operations researcher who uses DP, I will say that for the most part, OR treats DP as a decision-making tool, i.e., a method for mathematical optimization, as you say.

There are cases in which we try to discern special structure within the solution to the DP. For example, in inventory theory, we use the structure of the DP model to prove that the optimal policy has a certain structure, a structure that is much simpler than having to provide the whole table of action values for each state. But this is maybe an exception rather than the rule.

  • $\begingroup$ Are the “certain structures” necessarily overlapping or recursive? $\endgroup$ – Jiapeng Zhang Jun 10 at 21:47
  • $\begingroup$ @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/…. $\endgroup$ – LarrySnyder610 Jun 11 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.