Dynamic programming

related topics
{math, number, function}
{rate, high, increase}
{@card@, make, design}
{line, north, south}
{work, book, publish}

In mathematics and computer science, dynamic programming 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 which are only slightly smaller[1] and optimal substructure (described below). When applicable, the method takes far less time than naïve methods.

Top-down dynamic programming simply means storing the results of certain calculations, which are later used again since the completed calculation is a sub-problem of a larger calculation. Bottom-up dynamic programming involves formulating a complex calculation as a recursive series of simpler calculations.

Contents

History

The term dynamic programming 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 refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions,[2] and the field was thereafter recognized by the IEEE as a systems analysis and engineering topic. 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.

Full article ▸

related documents
Prime number theorem
Multivariate normal distribution
Computable number
Hyperreal number
Group action
Fundamental group
Abelian group
Convolution
Factorial
Continuous function
Frame problem
Primitive recursive function
Euler's formula
Dual space
Fundamental theorem of algebra
Basis (linear algebra)
Bessel function
BCH code
Ackermann function
Proofs of Fermat's little theorem
Probability theory
Monte Carlo method
Halting problem
Simplex
Fermat number
Compass and straightedge constructions
Lp space
Central limit theorem
Absolute value
REXX