In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Figure 1. ...

The term was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he had refined this to the modern meaning. The field was founded as a systems analysis and engineering topic which is recognized by the IEEE. Bellman's contribution is remembered in the name of the Bellman equation, a central result of dynamic programming which restates the optimization problem in recursive form. This article does not cite any references or sources. ... Richard Ernest Bellman (1920–1984) was an applied mathematician, celebrated for his invention of dynamic programming in 1953, and important contributions in other fields of mathematics. ... Year 1953 (MCMLIII) was a common year starting on Thursday (link will display full calendar) of the Gregorian calendar. ... This article does not cite its references or sources. ... Engineering is the applied science of acquiring and applying knowledge to design, analysis, and/or construction of works for practical purposes. ... The Institute of Electrical and Electronics Engineers or IEEE (pronounced as eye-triple-ee) is an international non-profit, professional organization incorporated in the State of New York, United States. ... A Bellman equation (also known as a dynamic programming equation), named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. ... A visual form of recursion known as the Droste effect. ...

The word "programming" in "dynamic programming" has no particular connection to computer programming at all, and instead comes from the term "mathematical programming", a synonym for optimization. Thus, the "program" is the optimal plan for action that is produced. For instance, a finalized schedule of events at an exhibition is sometimes called a program. Programming, in this sense, means finding an acceptable plan of action. Computer programming (often simply programming) is the craft of implementing one or more interrelated abstract algorithms using a particular programming language to produce a concrete computer program. ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ...

Overview

Figure 1. Finding the shortest path in a graph using optimal substructure; a straight line indicates a single edge; a wavy line indicates a shortest path between the two vertices it connects (other nodes on these paths are not shown); the bold line is the overall shortest path from start to goal.

Optimal substructure means that optimal solutions of subproblems can be used to find the optimal solutions of the overall problem. For example, the shortest path to a goal from a vertex in a graph can be found by first computing the shortest path to the goal from all adjacent vertices, and then using this to pick the best overall path, as shown in Figure 1. In general, we can solve a problem with optimal substructure using a three-step process: A diagram demonstrating solving the shortest path problem using optimal substructure. ... A diagram demonstrating solving the shortest path problem using optimal substructure. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...

1. Break the problem into smaller subproblems.
2. Solve these problems optimally using this three-step process recursively.
3. Use these optimal solutions to construct an optimal solution for the original problem.

The subproblems are, themselves, solved by dividing them into sub-subproblems, and so on, until we reach some simple case that is easy to solve.

Figure 2. The subproblem graph for the Fibonacci sequence. That it is not a tree but a DAG indicates overlapping subproblems.

To say that a problem has overlapping subproblems is to say that the same subproblems are used to solve many different larger problems. For example, in the Fibonacci sequence, F₃ = F₁ + F₂ and F₄ = F₂ + F₃ — computing each number involves computing F₂. Because both F₃ and F₄ are needed to compute F₅, a naïve approach to computing F₅ may end up computing F₂ twice or more. This applies whenever overlapping subproblems are present: a naïve approach may waste time recomputing optimal solutions to subproblems it has already solved. Image made by Derrick Coetzee is Adobe Illustrator and Photoshop to demonstrate overlapping subproblems in the Fibonacci sequence for the dynamic programming page. ... Image made by Derrick Coetzee is Adobe Illustrator and Photoshop to demonstrate overlapping subproblems in the Fibonacci sequence for the dynamic programming page. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. ... In mathematics, the Fibonacci numbers form a sequence defined recursively by: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ...

In order to avoid this, we instead save the solutions to problems we have already solved. Then, if we need to solve the same problem later, we can retrieve and reuse our already-computed solution. This approach is called memoization (not memorization, although this term also fits). If we are sure we won't need a particular solution anymore, we can throw it away to save space. In some cases, we can even compute the solutions to subproblems we know that we'll need in advance. Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...

In summary, dynamic programming makes use of:

• Overlapping subproblems
• Optimal substructure
• Memoization

Dynamic programming usually takes one of two approaches: Figure 1. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...

• Top-down approach: The problem is broken into subproblems, and these subproblems are solved and the solutions remembered, in case they need to be solved again. This is recursion and memoization combined together.
• Bottom-up approach: All subproblems that might be needed are solved in advance and then used to build up solutions to larger problems. This approach is slightly better in stack space and number of function calls, but it is sometimes not intuitive to figure out all the subproblems needed for solving the given problem.

Some programming languages can automatically memoize the result of a function call with a particular set of arguments, in order to speed up call-by-name evaluation (this mechanism is referred to as call-by-need). Some languages make it possible portably (e.g. Scheme, Common Lisp or Perl), some need special extensions (e.g. C++, see [1]). Some languages (e.g., Maple) have automatic memoization built in. In any case, this is only possible for a referentially transparent function. Top-down and Bottom-up are approaches to the software development process, and by extension to other procedures, mostly involving software. ... Top-down and Bottom-up are approaches to the software development process, and by extension to other procedures, mostly involving software. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... Parameters are a way of allowing the same sequence of commands to operate on different data without re-specifying the instructions. ... Parameters are a way of allowing the same sequence of commands to operate on different data without re-specifying the instructions. ... Scheme is a multi-paradigm programming language. ... Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard X3. ... Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose programming language with high-level and low-level capabilities. ... Maple 9. ... Referential transparency is a property of parts of computer programs. ...

Examples

A naive implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition: In mathematics, the Fibonacci numbers form a sequence defined recursively by: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ...

 function fib(n) if n = 0 or n = 1 return 1 else return fib(n − 1) + fib(n − 2) 

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

In particular, fib(2) was calculated twice from scratch. In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm.

Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(n) time instead of exponential time: An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

 var m := map(0 → 1, 1 → 1) function fib(n) if map m does not contain key n m[n] := fib(n − 1) + fib(n − 2) return m[n] 

This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values. Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...

In the bottom-up approach we calculate the smaller values of fib first, then build larger values from them. This method also uses linear (O(n)) time since it contains a loop that repeats n − 1 times:

 function fib(n) var previousFib := 0, currentFib := 1 repeat n − 1 times var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return currentFib 

In both these examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.

Checkerboard

Consider a checkerboard with n × n squares and a cost-function c(i, j) which returns a cost associated with square i,j (i being the row, j being the column). For instance (on a 5 × 5 checkerboard),

Thus c(1, 3) = 5

Let us say you had a checker that could start at any square on the first rank (i.e., row) and you wanted to know the shortest path (sum of the costs of the visited squares are at a minimum) to get to the last rank, assuming the checker could move only diagonally left forward, diagonally right forward, or straight forward. That is, a checker on (1,3) can move to (2,2), (2,3) or (2,4).

This problem exhibits optimal substructure. That is, the solution to the entire problem relies on solutions to subproblems. Let us define a function q(i, j) as

q(i, j) = the minimum cost to reach square (i, j)

If we can find the values of this function for all the squares at rank n, we pick the minimum and follow that path backwards to get the shortest path.

It is easy to see that q(i, j) is equal to the minimum cost to get to any of the three squares below it (since those are the only squares that can reach it) plus c(i, j). For instance:

Now, let us define q(i, j) in little more general terms:

This equation is pretty straightforward. The first line is simply there to make the recursive property simpler (when dealing with the edges, so we need only one recursion). The second line says what happens in the first rank, so we have something to start with. The third line, the recursion, is the important part. It is basically the same as the A,B,C,D example. From this definition we can make a straightforward recursive code for q(i, j). In the following pseudocode, n is the size of the board, c(i, j) is the cost-function, and min() returns the minimum of a number of values:

 function minCost(i, j) if j < 1 or j > n return infinity else if i = 1 return c(i, j) else return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j) 

It should be noted that this function just computes the path-cost, not the actual path. We will get to the path soon. This, like the Fibonacci-numbers example, is horribly slow since it spends mountains of time recomputing the same shortest paths over and over. However, we can compute it much faster in a bottom up-fashion if we use a two-dimensional array q[i, j] instead of a function. Why do we do that? Simply because when using a function we recompute the same path over and over, and we can choose what values to compute first.

We also need to know what the actual path is. The path problem we can solve using another array p[i, j], a predecessor array. This array basically says where paths come from. Consider the following code:

 function computeShortestPathArrays() for x from 1 to n q[1, x] := c(1, x) for y from 1 to n q[y, 0] := infinity q[y, n + 1] := infinity for y from 2 to n for x from 1 to n m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x] := m + c(y, x) if m = q[y-1, x-1] p[y, x] := -1 else if m = q[y-1, x] p[y, x] := 0 else p[y, x] := 1 

Now the rest is a simple matter of finding the minimum and printing it.

 function computeShortestPath() computeShortestPathArrays() minIndex := 1 min := q[n, 1] for i from 2 to n if q[n, i] < min minIndex := i min := q[n, i] printPath(n, minIndex) 

 function printPath(y, x) print(x) print("<-") if y = 2 print(x + p[y, x]) else printPath(y-1, x + p[y, x]) 

Sequence alignment

The steps for using dynamic programming to perform sequence alignment are as follows:

• Initialization - The first step in setting up a global alignment sequence. Set up a matrix by filling in the first row and column with zeros since it's assumed there're no gap penalties

• Matrix Fill - Filling in the matrix requires finding a score for each sequence alignment. To do this we look at the left, top, and above and diagonally left to reach the score of the alignment. If there's a match, +1, if there's a mismatch, 0, and if there's a gap, -1. Do this for all alignments until the matrix is filled up

• Traceback - This step determines the actual alignments that result in the maximum score. We do this by starting at the lower right corner and taking the upper box, the box to the left, and the box diagonally up. We pick the box that gives us the best score. Repeat this till we get to the top right corner, this is our maximum alignment.

Algorithms that use dynamic programming

• Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring.
• The Cocke-Younger-Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar
• The use of transposition tables and refutation tables in computer chess
• The Viterbi algorithm (used for hidden Markov models)
• The Earley algorithm (a type of chart parser)
• The Needleman-Wunsch and other algorithms used in bioinformatics, including sequence alignment, structural alignment, RNA structure prediction.
• Levenshtein distance (edit distance)
• Floyd's All-Pairs shortest path algorithm
• Optimizing the order for chain matrix multiplication
• Pseudopolynomial time algorithms for the Subset Sum and Knapsack and Partition problem Problems
• The dynamic time warping algorithm for computing the global distance between two time series
• The Selinger (a.k.a System R) algorithm for relational database query optimization
• De Boor algorithm for evaluating B-spline curves
• Duckworth-Lewis method for resolving the problem when games of cricket are interrupted
• The Value Iteration method for solving Markov decision processes
• Some graphic image edge following selection methods such as the "magnet" selection tool in Photoshop
• Interval scheduling
• Word wrap
• Travelling salesman problem

In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... The longest common subsequence problem (LCS) is finding a longest sequence which is a subsequence of all sequences in a set of sequences (often just two). ... The longest increasing subsequence problem is to find the longest increasing subsequence of a given sequence. ... The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. ... The Cocke-Younger-Kasami (CYK) algorithm (alternatively called CKY) determines whether a string can be generated by a given context-free grammar and, if so, how it can be generated. ... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ... In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. ... 1990s Pressure-sensory Chess Computer with LCD screen The idea of creating a chess-playing machine dates back to the eighteenth century. ... The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ... State transitions in a hidden Markov model (example) x — hidden states y — observable outputs a — transition probabilities b — output probabilities A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to... The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. ... A chart parser is a type of parser commonly used for natural languages that uses a data-driven approach based on a set of grammatical rules and a dictionary with each of the possible grammatical senses of each word indicated. ... The Needleman-Wunsch algorithm performs a global alignment on two sequences (called A and B here). ... Map of the human X chromosome (from the NCBI website). ... In bioinformatics, a sequence alignment is a way of arranging the primary sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. ... Structural alignment of thioredoxins from humans and the fly Drosophila melanogaster. ... The functional form of single stranded RNA molecules (like proteins) frequently requires a specific tertiary structure. ... In information theory and computer science, the Levenshtein distance is a string metric which is one way to measure edit distance. ... In computer science, the Floyd–Warshall algorithm (sometimes known as the Roy–Floyd algorithm, since Bernard Roy described this algorithm in 1959) is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. ... Matrix chain multiplication is an optimization problem that can be solved using dynamic programming. ... The subset sum problem is an important problem in complexity theory and cryptography. ... Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under 15 kg? A multi dimensional problem could consider the density or dimensions of the boxes, the latter a typical packing problem. ... The Partition problem is an NP-Complete problem in Computer Science. ... Dynamic time warping is an algorithm for measuring similarity between two sequences which may vary in time or speed. ... System R is a database system built as a research project at IBM San Jose Research (now IBM Almaden Research Center) in the 1970s. ... In the mathematical subfield of numerical analysis the De Boor algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. ... In the sport of cricket, the Duckworth-Lewis method (D/L method) is a mathematical way to calculate the target score for the team batting second in a one-day cricket match interrupted by weather or other circumstance. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Adobe Photoshop is a bitmap graphics editor (with some text and vector graphics capabilities) published by Adobe Systems. ... Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. ... Word wrap refers to a feature supported by most text editors that allows them to insert soft returns (or hard returns for some text editors) at the right-side margins of a document. ... If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A? The traveling salesman problem (TSP) is a problem in discrete or combinatorial optimization. ...

See also

• Bellman equation
• Markov Decision Process

A Bellman equation (also known as a dynamic programming equation), named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

References

• Adda, Jerome, and Cooper, Russell, 2003. Dynamic Economics. MIT Press. An accessible introduction to dynamic programing in economics. The link contains sample programs.
• Bertsekas, D. P., 2000. Dynamic Programming and optimal Control, Vols. 1 & 2, 2nd ed. Athena Scientific. ISBN 1-886529-09-4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. Especially pp. 323–69.
• Giegerich, R., Meyer, C., and Steffen, P., 2004, "A Discipline of Dynamic Programming over Sequence Data," Science of Computer Programming 51: 215-263.
• Nancy Stokey, and Robert E. Lucas, with Edward Prescott, 1989. Recursive Methods in Economic Dynamics. Harvard Univ. Press.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Nancy Stokey is a professor of economics at the University of Chicago. ... Robert Emerson Lucas, Jr. ... Edward C. Prescott, born 26 December 1940 in Glen Falls/New York, received the Bank of Sweden Prize in Economic Sciences in Memory of Alfred Nobel in 2004, sharing the award with Finn E. Kydland, for their contributions to dynamic macroeconomics: the time consistency of economic policy and the driving...

External links

• Dyna, a declarative programming language for dynamic programming algorithms
• Wagner, David B., 1995, "Dynamic Programming." An introductory article on dynamic programming in Mathematica.
• Ohio State University: CIS 680: class notes on dynamic programming, by Eitan M. Gurari
• A Tutorial on Dynamic programming
• More DP Notes
• Algorithmist's Dynamic Programming Contains more examples of Dynamic Programming.
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." An introduction to dynamic programming as an important tool in economic theory.
• Dynamic Programming: from novice to advanced A TopCoder.com article by Dumitru on Dynamic Programming
• Algebraic Dynamic Programming - a formalized framework for dynamic programming, including an entry-level course to DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
• Example of calculating Fibonacci numbers using dynamic programming, C++
• Dynamic programming tutorial
• An Introduction to Dynamic Programming