Hacker Newsnew | comments | show | ask | jobs | submit login

"...dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve. (Note: Not the technical definition)"

Is the author trying to redefine what Dynamic Programming means or is he just totally confusing its reader by actually using a DP algo but saying he's not using the technical definition!?

I mean: he's basically saying that Dynamic Programming is "Divide and Conquer". I'm not sure I follow him.

Especially seen that, contrarily to memoization (yes, "memoization", not "memorization", there's no 'r'), DP doesn't just compute and cache what's necessary but computes everything. In that DP really doesn't look like "a subproblem which is easier to solve".

Dynamic programming has a very precise meaning:

http://en.wikipedia.org/wiki/Dynamic_programming




He just said that it wasn't the technical definition for the simple language used. The note is not directly related to the algorithm he then explains.

Dynamic Programming can be seen as divide and conquer but using memoization to avoid recalculations.

The "subproblems easier to solve" are not easier complexity-wise but easier in the sense that we are solving a smaller subinstance of the main problem.

-----


I'm glad you have my back, adcoelho :D . @martinced, as adcoelho stated, I gave that disclaimer because I wanted to make sure that the reader knew that I gave a very rough definition that I hoped would be easier to understand, but was not rigorous. If the reader wants the rigorous definition and proof of this concept, there already are many resources on the internet for that.

-----




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: