Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested orders. The more I think about it, the more I feel strongly that the dynamic programming solution considers all possible chain orders, thus contradicting the justification of choosing a dynamic programming approach to solving this problem.

For Eg. Lets consider a product of 4 matrices. There are 5 possible matrix chain orders (in the brute force method)

(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Now, if we consider the dynamic programming approach all the sub matrix products included in each of the orders above will be computed. How then is the dynamic programming approach more efficient than the brute force approach?

EDIT: The answers and the comments have been really useful in helping me understand the DP solution better. But I am not able to visualise a brute force approach  in my head. As soon as I start writing a brute force method to compute all possible matrix multiplication orders, the DP solution manifests itself naturally in my attempt. This may be because I know the optimized DP solution and I am not able to think of a rudimentary brute force solution. If someone can mention the pseudo code for generating all possible matrix multiplication orders , it will make it clearer as to what sub-problems the DP solution avoids and hence is more efficient.

EDIT (again): Let us disregard memoization. Will the DP solution still generate lesser number of computations?
The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute.

A real brute force takes exponential time, the number of binary trees, which is equal to the number of nested expressions. See Catalan numbers.