动态规划——ACM兴趣小组辅导

本文主要是介绍动态规划——ACM兴趣小组辅导，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、矩阵连乘问题

１.两个矩阵乘积所需的计算量

void matrixMultiply(int **a, int **b, int **c, int ra, int ca, int rb, int cb)

{

if(ca!=rb) return;

for(int i=0; i<ra; ++i)

for(int j=0; j<cb; ++j)

{

int sum = a[i][0] * b[0][j];

for(int k=1; k<ca;++k)

sum += a[i][k] * a[k][j];

c[i][j] = sum;

}

可见需三重循环，总共要ra*ca*cb次数乘。

2.矩阵连乘时，加括号方式影响整个计算量。A₁A₂A₃（10×100,　100×5,　5×50），如（A₁A₂）A₃需要7500次，而A₁（A₂A₃）需要75000次,两者相差10倍。矩阵连乘问题就是求A₁A₂...A_n个矩阵的计算次序使得所需计算量最少，其中矩阵的行列存储在数据p中，A₁为p₀×p₁,A₂为p₁×p₂。

3.分析

设计算A[i:j],1≤i≤j≤n，所需的最少数乘次数为m[i][j]，则显然原问题的最少数乘次为m[1][n]。

若计算A_i...A_j时在A_k和A_k+1之间断开，则m[i][j]=m[i][k]+m[k+1][j]+p_i-1p_kp_j。因为如果要想整个计算量最少，则A_i...A_k和A_k+1...A_j的计算量也必须最少。只要确定的k的位置，则就找到了一个断点。k只有i, i+1,...,j-1这几种可能。m[i][j]可递归地定义为：

。

4.利用递归直接计算a[i][j]。（其中s[i][j]保存的是断开点）

int RecurMatrixCahin(int i, int j)
{
   if(i == j) return 0;
    int u = RecurMatrixCahin(i,i)+RecurMatrixCahin(i+1,j)+p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for(int k=i+1; k<j;++k)
{
      int t = RecurMatrixCahin(i,k)+RecurMatrixCahin(k+1,j)+p[i-1]*p[k]*p[j];
       if(t < u)
     {
          u = t;
         s[i][j] = k;
     }
   }
    return u;
}