Dynamic Programming: Introductory Concepts

Abstract

Dynamic programming (DP) is a general purpose problem solving methodology based on problem decomposition. The idea is to decompose a “difficult” problem into a family of “related problems”—which are often, but not always, “easier” subproblems of the “difficult” problem. Its plan of attack is then to embed the “difficult” problem of interest—the target problem—in a family of modified problems, and to use a functional equation to relate the solutions to these modified problems to one another. The solution obtained for this functional equation yields the solution to the modified problems as well as to the target problem. This approach has an extremely wide scope of application, but in operation..