动态规划之矩阵连乘

动态规划：

• 将大问题划分为具有相同特征的小问题；
• 小问题之间往往相互联系；
• 从小问题一步步求解大问题。
  适合求解最优解问题

矩阵连乘问题描述

有n个矩阵连乘，如何找到最小的加括号方式以及最小的次数

疑问

A(35)A(57)A(7*2)的向乘次数和划分有关系吗？

(A(3*5)A(5*7))A(7*2)  相乘次数： (3*5*7)+(3*7)*2 = 147
A(3*5)(A(5*7)A(7*2))  相乘次数： (5*7*2)+3*(5*2) = 100

答案很明显是有关系的。

分析

求 A1A2A3…An
定义   AiAi+1…Ak…Aj-1Aj   子列， 可看成是Ai…Ak，Ak…Aj
确定k的位置，然后按照递归的思想来逐步解决
求得结果后，使i=1，j=n原问题即可求解。

建立递归关系（状态转移方程）

设
Ai…Aj相乘 的最小数乘次数存储于m[i][j]中。
S[i][j]存储最佳断开位置。
A1：P0*P1
A2：P1*P2
A3：P2*P3
…
Ai：Pi-1*Pi
Ai+1：Pi*Pi+1
…
An：Pn-1*Pn
P0*P1*P2…*Pn——n+1个  

当i=j时，m[i][j] = 0;
当i<j时，m[i][j] = m[i][k]+m[k+1][j]+Pi-1PkPj
k在i，j之间取值，取值范围为i<=k<j
有递推关系如下：

动态规划的最优子结构性质是：

问题的最优解包含了其子问题的最优解。
最优子结构性质是问题可用动态规划法求解的显著特征。
Ak+1…Aj，Ai…Ak的最优划分也包含在Ai…Aj的最优划分中

s[i][j]的确定方法：

对于Ai……Aj
k=i, (Ai)(...Aj)
k=i+1, (AiAi+1)(...Aj)
k=j-1, (AiAi+1...Aj-1)Aj
求出m[i][j]的最小k值，存入s[i][j]，

最后递归的由s[i][j]构造出最优解
代码如下：

void func(int n,int *p,int **m,int **s){
  int i,h,j,k,t ;
  for(i = 1 ; i <= n ; i++)  //i=j，m[i][j]=0
    m[i][i] = 0;
  for(h = 2 ; h <= n ; h++){  //链长h
    for(i = 1 ; i < n-h+1 ; i++){
      j = i+h-1;
      m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
      s[i][j] = i;
      for(k = i+1 ; k < j ; k++){
        t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
        if(t < m[i][j]){
          m[i][j] = t;
          s[i][j] = k;
        }
      }
    }
  }
}