Re:Dynamic Programming: Chain Matrix Multiplication
by HalcyonicStorm on Thursday January 31, 2013 @11:42AM
(#5145807)
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.
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.