目录
矩阵连乘问题简介举例说明并详细分析备注代码块测试结果
矩阵连乘问题简介1
设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。为方便起见，将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，(1<=k小于n),则其相应的完全加括号方式为((A1…Ak)(Ak+1…An))。即依此次序，先计算A[1:k]和A[k+1:n]，然后将计算结果相乘得到A[1:n]。依此计算次序，总计算量为A[1:k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[K+1,n]相乘的计算量。
矩阵连乘问题简介2
设计动态规划算法的第二步是递归的定义最优值，对于矩阵连乘积的最优计算次序问题，设计算A[i:j],1<=i<=j<=n,所需最少数乘次数为m[i][j],则原问题的最优值为m[1][n]。
当i==j时，A[i:j]=Ai为单一矩阵，无需计算，因此m[i][i]=0,i=0,1,2….,n。当i小于j时，可利用最优子结构性质计算m[i][j]。事实上，若计算A[i:j]的最优次序再Ak和Ak+1之间断开，i<=k小于j;则m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]。由于再计算之前并不知道k的位置，所以k还未确定，不过k的位置只有j-i中可能（因为i<=k小于j），即k∈{i,i+1,….,j-1}。因此k是这j-i个位置中使计算量达到最小的那个位置。从而m[i][j]可以递归定义为 
举例说明并详细分析
假设：计算矩阵连乘积A1A2A3A4A5A6其中各矩阵的维数分别是 A1(30X35) A1(35X15) A1(15X5) A1(5X10) A1(10X20) A1(20X25) 
有n个矩阵就有n+1个维数
设置数组m[MAX][MAX]为记录每一个i~j的连乘最小次数 数组s[MAX][MAX]为记录最小乘次时的分割点
例如，在计算m[2][5]时，依次递归式有： 
所以m[2][5]=7125;且k=3,因此s[2][5]=3;
备注
这里没有创建二维数组而是使用了二维指针 这里就涉及到了二维指针的malloc开拓空间问题 它是与一维指针的创建不同的 比如开拓一个4x5的二维指针数组
p=(int **)malloc(4*sizeof(int *));if (NULL==p) return; for (i=0;i<4;i++) { p[i]=(int *)malloc(5*sizeof(int)); }但是最后要用free释放内存。
代码块
#include<stdio.h>#include<stdlib.h>#define MAX 99999int MatrixChain(int n, int *p, int **m, int **s){ int i, j, r, k; int tmp; for (i = 0; i < n; i++) { m[i][i] = 0; //单一矩阵的最小乘次都是0 } for (r = 2; r <= n; r++)//连乘矩阵的个数从2开始 { for (i = 0; i <= n - r; i++)//i表示连乘矩阵中的第一个 从0开始 //当连乘矩阵个数是2个时，第4个便是6个矩阵中最后的开始点 为n-r { j = i + r - 1;//连乘矩阵的结束点 m[i][j] = MAX; for (k = i; k <= j - 1; k++) //在第一个与最后一个之间寻找合适的断开点，要从i开始 { //例如 在a[0]与a[1]间 m[0][0]+m[1][1]=0 p[0]*p[1]*p[2]=15750; tmp = m[i][k] + m[k + 1][j] + p[i] * p[k+1] * p[j+1]; if (tmp < m[i][j]) { m[i][j] = tmp; s[i][j] = k; } } } } return m[0][n - 1];//求的时6个矩阵相乘的最小乘次，下标从0开始传m[0][n-1];}void PRintChain(int i, int j, char **a, int **s){ if (i == j) { printf("%s", a[i]); } else { printf("("); PrintChain(i, s[i][j], a, s); PrintChain(s[i][j] + 1, j, a, s); printf(")"); }}int main(void){ int **m;//m[i][j]存储的是i+1到j+1的最小乘次，因为是从0开始 int **s;//s[i][j]存储的是i+1到j+1之间的最小乘次的分割点 int *p;//p[]存储的是每个矩阵的行与列 char **a;//a[][]存储的是矩阵编号 int i; int n; int ret; printf("请输入矩阵个数:/n"); scanf("%d", &n); m = (int **)malloc(n*sizeof(int *)); s = (int **)malloc(n*sizeof(int *)); p = (int *)malloc((n + 1)*sizeof(int));//n个矩阵会有n+1个数据 a = (char **)malloc(n*sizeof(char *)); for (i = 0; i < n; i++) { m[i] = (int *)malloc(n*sizeof(int)); s[i] = (int *)malloc(n*sizeof(int)); a[i] = (char *)malloc(n*sizeof(char)); }//此处是用malloc给二维指针数组创建空间 printf("请输入n+1个维数:/n"); for (i = 0; i < n + 1; i++) { scanf("%d", &p[i]); } /*for (i = 0;i < n; i++) { scanf("%c", &a[i]); }*/ a[0] = "A1"; a[1] = "A2"; a[2] = "A3"; a[3] = "A4"; a[4] = "A5"; a[5] = "A6"; ret = MatrixChain(n, p, m, s); printf("%d个数的", n); printf("Minest times:%d./n", ret); PrintChain(0, n - 1, a, s); free(p); free(s); free(m); free(a); system("pause"); return 0;}测试结果
