I am reading CLRS by myself and I am finding but difficult to understand few concepts.
Compared to Greedy, in Dynamic Programming we make choices globally and end up with optimal solution. I understood these concepts well with examples of Shortest path in Multi Graph and also by Knapsack Problem.
I am unable to understand how we are making choices dynamically in Matrix Chain. I have understood the recurrence relation, but I am not able to standard about dynamic decisions. (I understood that it has optimal substructure property)
How matrix chain algorithm would work if it is solved by Greedy Method ?
Thank you !
This problem can't be solved by greedy method.
for example, a matrix chain [3x2]•[2x3] •[3x4].
The consequence will be (([3x2]•[2x3]) •[3x4]) using greedy method, but the optimal answer is ([3x2]•([2x3] •[3x4])).
More details:https://www.cs.washington.edu/education/courses/421/04su/slides/matrixchain.pdf