UVa 348

From Algorithmist
Jump to navigation Jump to search

348 - Optimal Array Multiplication Sequence[edit]

Summary[edit]

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

Explanation[edit]

Suppose for matrices 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 . Straightforward dynamic programming: first calculate all as 0, then calculate all with , then with , , 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.

Input[edit]

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[edit]

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)))))))