{

int min = 999999999;

for (int k = i; k < j; k++)

{

int multiCnt = multi[i][k] + multi[k + 1][j] + dimension[i]*dimension[k+1]*dimension[j+1];

if (min > multiCnt)

min = multiCnt;

if (k==j-1)

multi[i][j] = min;

}

{

int *dimension; //用来记录各个矩阵维度，如果矩阵的维度是50*20,20*1,1*10,10*100，那么矩阵内的信息为50,20,1,10,100

int matrixCnt;

cout << "输入矩阵的个数";

cin >> matrixCnt;

dimension = new int[matrixCnt+1];

cout << "输入各个矩阵的维度：\n";

for (int i = 0; i < matrixCnt+1; i++)

cin >> dimension[i];

//multiplicationCnt是矩阵

int **multiplicationCnt = new int*[matrixCnt];

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

multiplicationCnt[i] = new int[matrixCnt];

//multiplicationCnt初始化

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

{

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

{

multiplicationCnt[i][j] = 0;

}

}

//动态规划计算,斜对角动态规划

for (int s = 0; s < matrixCnt;s++)//s表示multiplicationCnt[i][j]中j-i的大小，通过这个差值来实现斜对角访问

{

for (int i = 0; i < matrixCnt-s; i++)

{

int j = i + s;

matrixChain(multiplicationCnt,dimension,i, j);

}

}

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

{

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

{

cout<<multiplicationCnt[i][j]<<" ";

}

cout << endl;

}

cout << "Matrix Chain Multiplication minimal count is " << multiplicationCnt[0][matrixCnt - 1] << endl;

return 0;