Dynamic Programming Algorithm

From GM-RKB
Jump to navigation Jump to search

A dynamic programming algorithm is an iterative algorithm that follows strategy which is applicable to decomposable tasks whose optimal solution contains optimal solutions to its subtasks and solutions can be stored and reused in a bottom-up fashion.



References

2012

  • (Wikipedia, 2012) ⇒ http://en.wikipedia.org/wiki/Dynamic_programming
    • QUOTE: 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 naive methods.

      The key idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often, many of these subproblems are really the same. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or “memo-ized": the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.

      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.

2011

2009

2008

2005

1966

  • (Bellman, 1966) ⇒ Richard Bellman. (1966). “Dynamic Programming.” In: Science, 153(3731).

1957

  • (Bellman, 1957) ⇒ Richard Bellman. (1957). “Dynamic Programming.” Princeton University Press.

  1. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 'Algorithms', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html