Dynamic Programming

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/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s