写在所有的前面：
本文采用C/C++实现代码
目录
题目说明
题目
题目出处
广西大学oj
22级《算法设计与分析》第二次作业
链接：https://oj.gxu.edu.cn/contest/625/problem/0001
题目描述Description
输入Input
输出Output
样例Sample
输入：
3
10 100 5 50
输出：
7500
限制Hint
n ≤ 100
解答说明
方案1：最优分隔点法（动态规划）
解题思路
薛猫颚的腚《动态规划之矩阵连乘问题详细解读（思路解读+填表+代码）》
这位大佬的讲解超详尽了直接转链节！！！
https://blog.csdn.net/weixin_44952817/article/details/110124596
我对代码部分的注释做了一些优化（挑战本题最详尽代码注释）
代码实现
想用哪个语言就用对应的头文件
c语言头文件：
#include<stdio.h>
c++头文件
#include<iostream>
using namespace std;
主代码部分：（详尽版本1）
const int N = 110;//常量
int A[N];//矩阵规模
int m[N][N];//最优解需要做的乘法次数
int s[N][N];//最优解所经历的“分隔点k”
void MatrixChain(int n)
{
int r, i, j, k;//连乘矩阵个数r，连乘开始点i，连乘结束点j，分隔点k
for (i = 0; i <= n; i++)//初始化对角线
{
m[i][i] = 0;//单个矩阵乘法次数为 0
}
for (r = 2; r <= n; r++)//r个矩阵连乘
{
//r个矩阵的r-1个空隙中依次测试最优点
for (i = 1; i <= n - r + 1; i++)//测试区间连乘从i开始
{
j = i + r - 1;//到j结束，共r个
m[i][j] = m[i][i] + m[i + 1][j] + A[i - 1] * A[i] * A[j];//记录第一个分隔点对应乘法次数
s[i][j] = i;//记录第一个分隔点
for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];//临时记录当前分隔点对应乘法次数
if (t < m[i][j])//更新最优分隔点
{
m[i][j] = t;//从i到j的最优乘法次数
s[i][j] = k;//分隔点
}
}
}
}
}
void print(int i, int j)//打印当前连乘矩阵
{
if (i == j)//分隔到单个矩阵
{
printf("A[%d]", i);//输出该矩阵
return;//返回上一级
}
printf("(");//分隔前左括号
print(i, s[i][j]);//当前左端，到最优分隔点
print(s[i][j] + 1, j);//最优分隔点，到当前右端
printf(")");//分隔前右括号
}
int main()
{
int n;//n个矩阵
scanf("%d", &n);//输入
for (int i = 0; i <= n; i++)
{
scanf("%d", &A[i]);//输入n个矩阵的n+1个数据
}
MatrixChain(n);//动态规划遍历记录最优分隔点及其对应乘法次数，n为测试矩阵个数
printf("最佳添加括号的方式为：");
print(1, n);//打印所有矩阵的连乘方法（括号分隔表示）
printf("\n最小计算量的值为：%d\n", m[1][n]);//所有矩阵连乘的最优乘法次数
return 0;
}
主代码部分（题目对应版本）
只打印乘法次数
const int N = 110;//常量
int A[N];//矩阵规模
int m[N][N];//最优解需要做的乘法次数
int s[N][N];//最优解所经历的“分隔点k”
void MatrixChain(int n)
{
int r, i, j, k;//连乘矩阵个数r，连乘开始点i，连乘结束点j，分隔点k
for (i = 0; i <= n; i++)//初始化对角线
{
m[i][i] = 0;//单个矩阵乘法次数为 0
}
for (r = 2; r <= n; r++)//r个矩阵连乘
{
//r个矩阵的r-1个空隙中依次测试最优点
for (i = 1; i <= n - r + 1; i++)//测试区间连乘从i开始
{
j = i + r - 1;//到j结束，共r个
m[i][j] = m[i][i] + m[i + 1][j] + A[i - 1] * A[i] * A[j];//记录第一个分隔点对应乘法次数
s[i][j] = i;//记录第一个分隔点
for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
{
int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];//临时记录当前分隔点对应乘法次数
if (t < m[i][j])//更新最优分隔点
{
m[i][j] = t;//从i到j的最优乘法次数
s[i][j] = k;//分隔点
}
}
}
}
}
int main()
{
int n;//n个矩阵
scanf("%d", &n);//输入
for (int i = 0; i <= n; i++)
{
scanf("%d", &A[i]);//输入n个矩阵的n+1个数据
}
MatrixChain(n);//动态规划遍历记录最优分隔点及其对应乘法次数，n为测试矩阵个数
printf("%d\n", m[1][n]);//所有矩阵连乘的最优乘法次数
return 0;
}
其他解释
大佬写的已经非常好了，这里仅做了一些输入输出代码上的修改（将头文件换掉可以跑c语言），和代码注释的详尽化，浅浅投一下稿啦
标签：连乘,分隔,int,矩阵,C++,最优,乘法 From： https://blog.csdn.net/just_do_it_sq/article/details/142218288