5 ms·
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
by adcoelho 14y ago
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.
- HalcyonicStorm 14y agoI'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.