In mathematics and computer science, dynamic programming is a method of solving problems that exhibit the properties of overlapping sub problems and optimal substructure. 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. The word "programming" in "dynamic programming" has no particular connection to computer programming at all, and instead comes from the term "mathematical programming", a synonym for optimization. Thus, the "program" is the optimal plan for action that is produced. For instance, a finalized schedule of events at an exhibition is sometimes called a program. Programming, in this sense, means finding an acceptable plan of action, an algorithm.
Dynamic programming usually takes one of two approaches, the top-down approach, the problem is broken into sub problems, and these sub problems are solved and the solutions remembered, in case they need to be solved again. This is recursion and memorization combined together and the bottom-up approach, all sub problems that might be needed are solved in advance and then used to build up solutions to larger problems. This approach is slightly better in stack space and number of function calls, but it is sometimes not intuitive to figure out all the sub problems needed for solving the given problem.
Some programming languages can automatically memorize the result of a function call with a particular set of arguments, in order to speed up call-by-name. Some languages make it possible portably (e.g. Scheme, Common Lisp or Perl), some need special extensions.This is only possible for a referentially transparent function.