矩阵连乘动态规划代码C语言

矩阵连乘问题是动态规划的一个重要例子，也是算法设计中的一个基本问题。它的目标是给定一系列矩阵，求在最少的乘法次数下将它们相乘的结果。由于矩阵乘法不满足交换律，因此乘法的次序会影响到最终结果，而不同的次序所需要的计算量也可能不同。因此，解决这个问题，可以通过枚举所有可能的乘法次序，得出每种次序下所需的计算量，然后从中选出最小的那个。但是，由于可能的乘法次序非常多，这个枚举方法并不适用。

动态规划算法的思想是将问题分解成一系列子问题，然后从最简单的子问题开始逐步求解，直到求出原问题的解。在矩阵连乘问题中，我们可以将连乘的序列划分成若干段，每一段中包含相邻的矩阵。这样，我们就可以将原问题转化为若干个子问题，每个子问题都是相邻矩阵的连乘问题。然后，可以利用子问题的解来推导出原问题的解。

为了方便描述，我们用m[i,j]表示将矩阵Ai到Aj相乘所需的最少乘法次数。因为连乘的两个矩阵A和B的行列数分别为p*q和q*r，所以它们的乘积矩阵C的行列数为p*r，它们相乘所需的乘法次数为p*q*r。因此，对于两个相邻的矩阵Ai和Ai+1，我们可以得到它们相乘所需的乘法次数为mi*mi+1*mi+2，其中mi表示Ai的行数，mi+1表示Ai+1的行数，mi+2表示Ai+1的列数。

基于这个思想，我们可以得到矩阵连乘动态规划的算法步骤：

1. 初始化。将所有m[i,i]初始化为0，表示单个矩阵相乘所需的乘法次数为0。

2. 计算子问题的解。从矩阵连乘的长度为2开始，依次计算所有子问题的解。具体地，在计算长度为k的连乘问题时，枚举所有可能的分割点i，将连乘问题(Ai...Aj)划分成两部分(Ai...Ai+i-1)和(Ai+i...Aj)，然后利用m[i,i+i-1]和m[i+1,j]计算出m[i,j]=m[i,i+i-1]+m[i+1,j]+mi*mi+i*mi+1。

3. 返回解。当计算出所有子问题的解之后，原问题的解即为m[1,n]。

代码实现：

```

#include

#define INF 10000000

int matrixChain(int p[], int n, int m[][100], int s[][100]) {

int i,j,k,len;

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

m[i][i] = 0;

}

for(len=2; len<=n; ++len) {

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

j = i+len-1;

m[i][j] = INF;

for(k=i; k

int tmp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if(tmp

m[i][j] = tmp;

s[i][j] = k;

}

}

}

}

return m[1][n];

}

void printOptimalParens(int s[][100], int i, int j) {

if(i==j) {

printf("A%d", i);

} else {

putchar('(');

printOptimalParens(s, i, s[i][j]);

printOptimalParens(s, s[i][j]+1, j);

putchar(')');

}

}

int main() {

int p[100];

int n = 6; //矩阵数量

int m[100][100] = {0};

int s[100][100] = {0};

p[0] = 30; //第一个矩阵的行数

p[1] = 35; //第一个矩阵的列数，也是第二个矩阵的行数

p[2] = 15; //第二个矩阵的列数，也是第三个矩阵的行数

p[3] = 5;

p[4] = 10;

p[5] = 20; //最后一个矩阵的列数

int res = matrixChain(p, n, m, s);

printf("Minimum multiplication cost: %d\n", res);

printf("Optimal parenthesization: ");

printOptimalParens(s, 1, n);

putchar('\n');

return 0;

}

```