Using the Matrix Chain with Greedy method

Question

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.

1. 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)

2. How matrix chain algorithm would work if it is solved by Greedy Method ?

Thank you !

Answer 1

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