Cormen DP page 335
At this point, it is a simple matter to write a recursive algorithm based on recurrence
(15.12) to compute the minimum cost m[1, n] for multiplying A1 A2 · · · An .
As we shall see in Section 15.3, however, this algorithm takes exponential time,
which is no better than the brute-force method of checking each way of parenthesizing
the product.
The important observation that we can make at this point is that we have relatively
few subproblems: one problem for each choice of i and j satisfying
1 ≤ i ≤ j ≤ n, or
n chose 2 +n ^2=O(n^2)
How do we deduce it is n choose 2 + n^2 =O(n2)?
