Dynamic Programming

Introduction

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure (described below). When applicable, the method takes far less time than naive methods.

Overview

Dynamic programming is both a mathematical optimization method and a computer programming method. 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.

A computer screen displaying a dynamic programming algorithm.

History

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.

Bellman's contribution is remembered in the name of the Bellman equation, a central result of dynamic programming which restates an optimization problem in recursive form.

Properties

Dynamic programming is characterized by the presence of overlapping subproblems and optimal substructure:

- Overlapping subproblems: This means that the space of subproblems must be small, i.e., any recursive algorithm solving the problem should solve the same subproblems over and over, rather than generating new subproblems. - Optimal substructure: If an optimal solution contains an optimal solution to a subproblem, then we can solve that subproblem first and incorporate its solution into our solution.

Applications

Dynamic programming has many applications, in fields such as mathematics, computer science, economics, and bioinformatics. Some examples include:

- In mathematics, it is used for solving optimization problems. - In computer science, it is used for algorithm design, including the knapsack problem, sequence alignment, shortest path in a graph, and many others. - In economics, it is used to solve problems involving constrained optimization, like maximizing income under certain budget constraints. - In bioinformatics, it is used for sequence alignment, protein folding, RNA structure prediction, and other problems.

Dynamic Programming in Computer Science

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.

Typically, dynamic programming algorithms are used for optimization. A dynamic programming algorithm will examine all possible answers to a problem and pick the best solution. Therefore, we can roughly describe dynamic programming as an intelligent, brute-force method that allows us to go through all possible solutions to pick the best one. If the scope of the problem is such that going through all possible solutions is possible and fast enough, dynamic programming guarantees finding the optimal solution.

The alternatives are many, such as using a greedy algorithm, which picks the best choice "at any possible step". While a greedy algorithm does not guarantee the optimal solution, it is faster. However, by making the best choice at each step, the greedy algorithm also attempts to find a global optimum from a local optimum. This isn't always successful, as the correct choice at each step depends on knowing future outcomes.

Dynamic Programming in Economics

In economics and finance, dynamic programming is used in many different areas, including but not limited to: optimal consumption and savings; optimal control of inventories; option valuation; and when and whether to invest in a certain project. As above, the problem is "solved" by solving a sequence of simpler (smaller) problems.

Dynamic Programming in Mathematics

In mathematics, dynamic programming is used for solving optimization problems. One example of an optimization problem is the "travelling salesman problem" (TSP). This problem asks for the shortest possible route through a given set of cities, visiting each city exactly once and returning to the original city. A brute-force approach would involve generating all permutations of the cities and checking the total distance travelled for each permutation. However, this approach is not feasible for large numbers of cities. Dynamic programming takes a more efficient approach by breaking the problem down into smaller subproblems and solving each of those only once.