Dynamic programming (DP) is not a specific algorithm, but a technique to design an efficient algorithm for a specific problem, and DP problems are particularly those problems which this technique can be applied to.

*Memoization* is a usual way to speedup a recursive algorithm. Dynamics Programming ≠ recursion + memoization, although a dynamic programming algorithm usually appears applying memoization technique to a recursive algorithm, for example, fibonacci sequence. There are some DP problems which cannot be implemented as a recursive function with memoization, e.g. Egg Dropping puzzle, see [1].

There is a thoughtful discussion in stackexchange.com[2]. However, the comments from Rapheal might not be accurate, for the conditions given by the author are too general, which is applicable for divid-and-conquer technique. The critical one which is missing is the property of **overlapping** **subproblems**. That is the watershed between dynamic programming and divid-and-conque. The overlapping

In the wikipedia[1], it is stated that the dynamic programming is applicable to the problems exhibiting the properties of **overlapping subproblems** and **optimal substructure,** which is not accurate, either. Not all

[1] https://en.wikipedia.org/wiki/Dynamic_programming

[2] http://cs.stackexchange.com/questions/2057/when-can-i-use-dynamic-programming-to-reduce-the-time-complexity-of-my-recursive

[3]http://people.cs.clemson.edu/~bcdean/dp_practice/

### Like this:

Like Loading...

*Related*