Compute optimal matrix multiplication order

Given an array dims[0..n] where matrix i has dimensions dims[i-1] × dims[i] (for i = 1..n), compute the minimum number of scalar multiplications needed to multiply the chain M1…Mn. Return both the minimal cost and one optimal parenthesization. Analyze time and space complexity. Follow-ups: reduce space to O(n^ 2); handle an extra fixed setup cost per multiplication; compare bottom-up DP vs. top-down memoization.

Optimal Matrix Chain Multiplication Order

Given an integer array dims of length n+1 (n >= 1), where matrix Ai has dimensions dims[i-1] x dims[i] for i = 1..n, compute the minimum number of scalar multiplications needed to multiply the chain A1...An. Return both the minimal cost and one optimal fully parenthesized order as a string built from 'A1'..'An' with parentheses and no spaces. If n = 1, return cost 0 and 'A1'. If multiple optimal orders exist, return any one of them.

Constraints

• 2 <= len(dims) <= 200
• 1 <= dims[i] <= 10^4
• The number of matrices is n = len(dims) - 1
• Return a fully parenthesized string; matrices are named A1..An

Examples

Example 1

Input: dims = [30,35,15,5,10,20,25]
Output: cost = 15125, order = ((A1(A2A3))((A4A5)A6))

Explanation: Optimal grouping multiplies A2A3 and A4A5 first, then combines with A1 and A6, totaling 15125 scalar multiplications.

Example 2

Input: dims = [10,100,5,50]
Output: cost = 7500, order = ((A1A2)A3)

Explanation: Compute (A1A2) first (cost 101005=5000), then multiply by A3 (10550=2500), total 7500.

Hints

1. Let m[i][j] be the minimal cost to multiply Ai..Aj; try all splits k in [i..j-1].
2. Transition: m[i][j] = min_k m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j].
3. Store the argmin split to reconstruct a parenthesization.
4. Initialize m[i][i] = 0 and build solutions by increasing chain length.
5. Top-down memoization yields the same recurrence if you prefer recursion.

Approach

Use bottom-up dynamic programming. m[i][j] stores the minimal scalar multiplications to compute the product Ai..Aj. For each chain length L and start i, try all split positions k between i and j and choose the one minimizing m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j]. Store the argmin in s to reconstruct a fully parenthesized order via recursion. Base case m[i][i] = 0 yields cost 0 for a single matrix. The result is m[1][n] and the reconstructed order.

• Time complexity: O(n^3)
• Space complexity: O(n^2)