Published Sep 02, 2022
[
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.
If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.[1] In the optimization literature this relationship is called the Bellman equation.
There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called “divide and conquer” instead.[1] This is why merge sort and 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 p1 from u to w and p2 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
series: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Then F43 = F42 + F41,
and F42 = F41 + F40. Now F41 is being solved in the recursive sub-trees of
both F43 as well as F42. 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.
This can be achieved in either of two ways:
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. 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.
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 F41 and F40, we can directly
calculate the value of F42.