Dynamic programming

Dynamic programming
Name	Dynamic programming
Class	Optimization (mathematics), Algorithmic paradigm
Inventor	Richard Bellman
Year	1950s

Dynamic programming. It is a powerful method for solving complex problems by breaking them down into simpler, overlapping subproblems, solving each only once, and storing their solutions for future reference. This approach is fundamental to Computer science and Operations research, providing efficient solutions to problems that exhibit Optimal substructure and Overlapping subproblems. Its development is credited to Richard Bellman at the RAND Corporation, and it has become a cornerstone technique in fields ranging from Bioinformatics to Economics.

Overview

Dynamic programming is a mathematical optimization technique and a foundational concept in Algorithm design. Unlike Brute-force search, it systematically explores a problem's state space by storing intermediate results, often in a Table (information) or Array data structure. This paradigm is closely related to Recursion (computer science) and Divide and conquer algorithm, but is distinguished by its explicit use of memory to avoid redundant calculations. The method is formally applied to problems within Discrete mathematics and is a standard topic in computer science curricula worldwide, such as those at MIT and Stanford University.

Core concepts

The two defining properties of problems solvable by this method are optimal substructure and overlapping subproblems. Optimal substructure, a principle also central to Greedy algorithm design, means an optimal solution can be constructed efficiently from optimal solutions of its subproblems. Overlapping subproblems occur when a recursive algorithm revisits the same problem repeatedly, as famously seen in the naive computation of the Fibonacci number sequence. To manage this, solutions are stored through Memoization or a bottom-up tabulation approach, concepts further explored in works by Donald Knuth and Thomas H. Cormen. The Bellman equation provides the recursive formulation for many such problems.

Examples

Classic illustrative problems include the Knapsack problem, the Longest common subsequence problem vital to Sequence alignment, and the Shortest path problem as solved by the Bellman–Ford algorithm. Computing the Edit distance between two strings, a key operation in Spell checker development and DNA sequencing, is another canonical example. The technique is also used to solve the Matrix chain multiplication problem for optimizing Compiler performance and the Coin problem in financial systems. The Viterbi algorithm, used in Hidden Markov models for Speech recognition and Cryptanalysis, is a prominent dynamic programming algorithm.

Applications

Its applications are vast and interdisciplinary. In Bioinformatics, it is essential for tasks like Genome assembly and Protein structure prediction. Within Economics, it is used for Optimal control in macroeconomic models and Stochastic programming in financial markets, influenced by the work of Robert C. Merton. Robotics utilizes it for Motion planning and Trajectory optimization, while in Artificial intelligence, it underpins algorithms for Game theory and Reinforcement learning, such as those used by DeepMind's AlphaGo. Other uses include Seam carving for Image editing, Text justification in Word processors, and optimizing yields in Petroleum industry operations.

Algorithms

Many famous algorithms are implementations of this paradigm. The Floyd–Warshall algorithm solves the All-pairs shortest path problem for graphs. The Cocke–Younger–Kasami algorithm is used for Parsing in Computational linguistics. The Needleman–Wunsch algorithm and Smith–Waterman algorithm are fundamental to Bioinformatics for Global alignment and Local alignment, respectively. For Resource allocation, the Dynamic programming in production planning approach is used. The development of these algorithms has been advanced by institutions like AT&T Bell Labs and researchers including Stephen Cook and Jon Bentley.

History and development

The field was pioneered and named by Richard Bellman in the 1950s while working at the RAND Corporation on Multistage decision processes for the United States Air Force. He deliberately chose the term "dynamic" to capture the time-varying nature of the problems and "programming" in the sense of Mathematical optimization, not Computer programming. Early influences included the work of John von Neumann on Game theory and the Manhattan Project. The method was later formalized in Bellman's seminal 1957 book, "Dynamic Programming". Its adoption accelerated with the rise of Computer engineering and was integral to the development of the Apollo program's guidance systems. Subsequent theoretical work by Ronald Howard on Markov decision processes and by Michael Held and Richard M. Karp on the Held–Karp algorithm for the Travelling salesman problem further solidified its importance.

Category:Algorithms Category:Mathematical optimization Category:Computer science