Dynamic Programming
Moshe Sniedovich · 2010
Dynamic programming (DP) is a general-purpose problem-solving paradigm. It is based on the proposition that in many situations a problem can be decomposed into a family of related problems so that the solution to the problem of interest (target problem) is expressed in terms of the solutions to these related problems (modified problems). Example To illustrate this idea, consider the network depicted in Fig. 1 , where the numbers on the arcs denote their lengths. Suppose that the problem of interest is to find the shortest path from node 1 to node 7, where the length of a path is equal to the sum of the arcs’ lengths on that path. Dynamic Programming, Fig. 1 A shortest path problem Full size image