DP---矩阵连乘
动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法，而是按不同输入给出问题的具体实例的子问题划分方法，然后再进行运算、解答问题。
矩阵连乘问题的主要思想如下：
1）设置大小为连乘个数的方阵
2）主对角线上方各元素Di,j(i<j)表示矩阵Mi连乘到Mj的最小工作量
3）下方元素Di,j(i>j)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号
最后通过下方元素可知最终结果的分组方式。
算法描述：
1）读入n, 即矩阵的个数;
2）读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中;
3）将d主对角线元素置为零;
4）求出d矩阵的其它元素的数值;
5）给出n个矩阵的结合方式.
Code：
#define MAXINT 1000int D[10][10],R[11];void print(int i, int j){int k;if(i==j) printf("M%d",i);else if (i+1==j) printf("M%d,M%d",i,j);else{k =D[j][i];printf(" (");print(i,k);print(k+1, j);printf(")");}}DM(int N){int I,J,K,T;for(I=1;I<N-1;I++)for(J=1;J<N-1;J++){D[J][J+1]=MAXINT;for(K=0;K<I-1;K++) {T=D[J][J+K]+D[J+K+1][J+1]+R[J-1]*R[J+K]*R[J+1];if(T<D[J][J+1]){D[J][J+1]=T;D[J][J+1]=J+K;}}}}main(){int flag=1,N,i;char c;printf("e------exit i--------continue\n");while(flag==1){scanf("%c",&c);switch(c){case 'i': flag=1;printf("Please Input The Data:\n");printf("The value of matrix: N="); scanf("%d",&N);for(i=0;i<N;i++){printf("R[i]=",i);scanf("%d",&R[i]);}for(i=1;i<N;i++) D[i][i]=0;DM(N);print(1,N+1);break;case 'e': flag=0;break;}}}