Editing Dynamic programming (section)

=== Computer science ===
There are two key attributes that a problem must have in order for dynamic programming to be applicable: [[optimal substructure]] and [[overlapping subproblem|overlapping sub-problem]]s. If a problem can be solved by combining optimal solutions to ''non-overlapping'' sub-problems, the strategy is called "[[Divide and conquer algorithm|divide and conquer]]" instead.<ref name=":0" />  This is why [[mergesort|merge sort]] and [[quicksort|quick sort]] are not classified as dynamic programming problems.

''Optimal substructure'' means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Such optimal substructures are usually described by means of [[recursion]]. For example, given a graph ''G=(V,E)'', the shortest path ''p'' from a vertex ''u'' to a vertex ''v'' exhibits optimal substructure: take any intermediate vertex ''w'' on this shortest path ''p''. If ''p'' is truly the shortest path, then it can be split into sub-paths ''p<sub>1</sub>'' from ''u'' to ''w'' and ''p<sub>2</sub>'' from ''w'' to ''v'' such that these, in turn, are indeed the shortest paths between the corresponding vertices (by the simple cut-and-paste argument described in ''[[Introduction to Algorithms]]''). Hence, one can easily formulate the solution for finding shortest paths in a recursive manner, which is what the [[Bellman–Ford algorithm]] or the [[Floyd–Warshall algorithm]] does.

''Overlapping'' sub-problems means that the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems. For example, consider the recursive formulation for generating the Fibonacci sequence: ''F''<sub>''i''</sub> = ''F''<sub>''i''&minus;1</sub> + ''F''<sub>''i''&minus;2</sub>, with base case ''F''<sub>1</sub>&nbsp;=&nbsp;''F''<sub>2</sub>&nbsp;=&nbsp;1. Then ''F''<sub>43</sub> =&nbsp;''F''<sub>42</sub>&nbsp;+&nbsp;''F''<sub>41</sub>, and ''F''<sub>42</sub> =&nbsp;''F''<sub>41</sub>&nbsp;+&nbsp;''F''<sub>40</sub>. Now ''F''<sub>41</sub> is being solved in the recursive sub-trees of both ''F''<sub>43</sub> as well as ''F''<sub>42</sub>. Even though the total number of sub-problems is actually small (only 43 of them), we end up solving the same problems over and over if we adopt a naive recursive solution such as this. Dynamic programming takes account of this fact and solves each sub-problem only once.

[[Image:Fibonacci dynamic programming.svg|thumb|108px|'''Figure 2.''' The subproblem graph for the Fibonacci sequence. The fact that it is not a [[tree structure|tree]] indicates overlapping subproblems.]]

This can be achieved in either of two ways:<ref>{{Cite web |title=Algorithms by Jeff Erickson |url=https://jeffe.cs.illinois.edu/teaching/algorithms/ |access-date=2024-12-06 |website=jeffe.cs.illinois.edu}}</ref>

* ''[[Top-down and bottom-up design|Top-down approach]]'': This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily [[memoize]] or store the solutions to the sub-problems in a table (often an [[Array (data structure)|array]] or [[Hash table|hashtable]] in practice). Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
* ''[[Top-down and bottom-up design|Bottom-up approach]]'': Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of ''F''<sub>41</sub> and ''F''<sub>40</sub>, we can directly calculate the value of ''F''<sub>42</sub>.

Some [[programming language]]s can automatically [[memoization|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 (programming language)|Scheme]], [[Common Lisp]], [[Perl]] or [[D (programming language)|D]]). Some languages have automatic [[memoization]] <!-- still not a typo for "memor-" --> built in, such as tabled [[Prolog]] and [[J (programming language)|J]], which supports memoization with the ''M.'' adverb.<ref>{{cite web|title=M. Memo|url=http://www.jsoftware.com/help/dictionary/dmcapdot.htm|work=J Vocabulary|publisher=J Software|access-date=28 October 2011}}</ref> In any case, this is only possible for a [[referentially transparent]] function. Memoization is also encountered as an easily accessible design pattern within term-rewrite based languages such as [[Wolfram Language]].