【算法导论】动态规划（二）矩阵链乘法

矩阵链乘法问题

矩阵乘法

两个矩阵A和B相乘，维度分别为$ p×q$和$ q×r$，则$A*B$的时间复杂度为$pqr$

MATRIX_MULTIPLY(A,B){
  for (int i = 0;i <A.rows;i++){
    for(int j = 0;j < B.cols;j++){
      for(int k = 0;k < A.cols;k++){
        C[i,j] = A[i,k]*B[k,j];
}}}}

矩阵链乘法

​ 首先，给定一个矩阵链 $<A_1,A_2,A_3>$ ，三个矩阵的规模分别为：10×100 ， 100×5 ，5×50 ，计算他们的乘积有两种方式：

$((A_1A_2)A_3)$	$10*100*5+10*5*50=7500$
$(A_1(A_2A_3))$	$100*5*50+10*100*50=75000$

可以看出，对一串矩阵做乘法操作，乘法的顺序影响到算法的时间复杂度。由此，引出矩阵链乘法问题：

给定n个矩阵的链$<A_1,A_2,...,A_n>$，矩阵$A_i$ 的规模为$p_{i-1} \times p_i$，确定代价最低的计算顺序，使得计算乘积$A_1A_2A_n$所需标量乘法次数最小。

用DP解决此问题

DP四步骤：

1. 可以将求解$A_1,*A_2*...*A_n$所需要的乘法次数问题划分成两个子问题：求解$A_1,*A_2*...*A_k$所需要的乘法次数+求解$A_{k+1},*A_{k+2}*...*A_n$所需要的乘法次数+$p_0*p_k*p_n$
2. ​