Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order
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.