MATRIX-MULTIPLY(A, B)

1 if columns[A] ≠ rows[B]

2     then error "incompatible dimensions"

3     else for i ← 1 to rows[A]                      //   rows[A]

4               do for j ← 1 to columns[B]           //   col[B]

5                       do C[i, j] ← 0

6                          for k ← 1 to columns[A]   //   col[A]

7                               do C[i, j] ← C[i, j] + A[i, k] · B[k, j]

8          return C

从上面的代码中，我们可以看出两个矩阵AB相乘，他们的操作次数为rows[A]*col[B]*col[A].知道这一点之后，我们看下面：

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

这下你应该清楚了题意吧。好，那我们下面想想怎么来减少它的次数。依然按照动态规划的算法流程来解决问题：

• 当(A1*A2)*A3时，此时K=2，即表示分界点为A2.
• 当A1*(A2*A3)时，此时K=1，即表示分界点为A1.

 1 // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

 2 MatrixChainOrder(int p[])

 3 {

 4     // length[p] = n + 1

 5     n = p.length - 1;

 6     // m[i,j] = Minimum number of scalar multiplications (i.e., cost)

 7     // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]

 8     // cost is zero when multiplying one matrix

 9     for (i = 1; i <= n; i++)

10        m[i,i] = 0;

11

12     for (L=2; L<=n; L++) { // L is chain length

13         for (i=1; i<=n-L+1; i++) {

14             j = i+L-1;

15             m[i,j] = MAXINT;

16             for (k=i; k<=j-1; k++) {

17                 // q = cost/scalar multiplications

18                 q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];

19                 if (q < m[i,j]) {

20                     m[i,j] = q;

21                     s[i,j]=k// s[i,j] = Second auxiliary table that stores k

22                                // k      = Index that achieved optimal cost

23

24                 }

25             }

26         }

27     }

28 }

 1 public class MatrixOrderOptimization {

 2     protected int[][]m;

 3     protected int[][]s;

 4     public void matrixChainOrder(int[] p) {

 5         int n = p.length - 1;

 6         m = new int[n][n];

 7         s = new int[n][n];

 8         for (int i = 0; i < n; i++) {

 9             m[i] = new int[n];

10             m[i][i] = 0;

11             s[i] = new int[n];

12         }

13         for (int ii = 1; ii < n; ii++) {

14             for (int i = 0; i < n - ii; i++) {

15                 int j = i + ii;

16                 m[i][j] = Integer.MAX_VALUE;

17                 for (int k = i; k < j; k++) {

18                     int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];

19                     if (q < m[i][j]) {

20                         m[i][j] = q;

21                         s[i][j] = k;

22                     }

23                 }

24             }

25         }

26     }

27     public void printOptimalParenthesizations() {

28         boolean[] inAResult = new boolean[s.length];

29         printOptimalParenthesizations(s, 0, s.length - 1, inAResult);

30     }

31     void printOptimalParenthesizations(int[][]s, int i, int j,  /* for pretty printing: */ boolean[] inAResult) {

32         if (i != j) {

33             printOptimalParenthesizations(s, i, s[i][j], inAResult);

34             printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);

35             String istr = inAResult[i] ? "_result " : " ";

36             String jstr = inAResult[j] ? "_result " : " ";

37             System.out.println(" A_" + i + istr + "* A_" + j + jstr);

38             inAResult[i] = true;

39             inAResult[j] = true;

40         }

41     }

42 }