# UVa 348

## Summary

Compute the optimal ordering of multiplications for all sequences of matrices of lengths 1 through n, in that order.

## Explanation

Suppose for matrices $A_{1}A_{2}...A_{n-1}A_{n}$ we know the optimal number of multiplications needed to multiply any consecutive sequence of less than n of the matrices. Then the optimal number of multiplications needed to multiply the n matrices is $a(1,n)=min[a(1,i)+a(i,n)+rows(A_{1})*rows(A_{i})*columns(B_{n}),1<=i<=n]$ . Straightforward dynamic programming: first calculate all $a(i,i)$ as 0, then calculate all $a(i,j)$ with $j-i=1$ , then with $j-i=2$ , $j-i=3$ , etc. Since we want the parenthesized expression rather than the optimal number of multiplications, we can simply store a partial solution at each stage, i.e., store a string "(A1 x (A2 x A3))" as b(1,3) in case 3 of the examples.

```3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
10
2 84
84 66
66 8
8 410
410 8
8 96
96 10
10 200
200 10
10 2
0
```

## Output

```Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
Case 4: (((A1 x A2) x A3) x (A4 x (A5 x (A6 x (A7 x (A8 x (A9 x A10)))))))
```