矩阵连乘：

#include<iostream>
#define inf 0x7fffffff
using namespace std;
int a[256] = { 0 };//存储矩阵的行和列 
int m[256][256] = { 0 };//存储i到j的最少计算次数 
int s[256][256] = { 0 };//存储i到j的中转站k 
void m_print(int i, int j)
{if (i == j){printf("M%d", i);}else{printf("(");m_print(i, s[i][j]);m_print(s[i][j] + 1, j);printf(")");}
}
int matrixMultiple()
{int n = 0;scanf("%d", &n);for (int i = 1; i <= n + 1; i++){scanf("%d", &a[i]);}for (int d = 2; d <= n; d++)//d个矩阵相乘 {for (int i = 1; i <= n - d + 1; i++)//斜着到第i个 {int j = i + d - 1;m[i][j] = inf;for (int k = i; k <= i + d - 2; k++){int temp = m[i][k] + m[k + 1][j] + a[i] * a[k + 1] * a[j + 1];if (temp < m[i][j]){m[i][j] = temp;s[i][j] = k;}}}}printf("%d ", m[1][n]);m_print(1, n);return 0;
}

输入个数为6，输入矩阵维度为：30，35，15，5，10，20，25

测试结果：

数据m截图：

数组s截图：