问题描述：
矩阵连乘问题是通过给矩阵连乘时加括号，使得总的计算量最小。

考虑3个矩阵相乘的例子， A1,A2,A3,假设这3个矩阵的维数分别为 10x100,100x50,5x50

若按照（（A1A2）A3）方式计算，需要的数乘次数为10x100x5+10x5x50 = 7500

若按照（A1(A2A3)）方式计算，需要的数乘次数为100x5x50+10x100x50 =75000

思路：
你可以理解为给你一个区间问你这个区间里面有多少种区间长度为2的组合。（可能说的不太清楚，举个例子）
如果 给你区间[1,3]，我们可以把这个区间拆成[1,1] + [2,3] 或者[1,2]+[3,3]，那么问题就是保证区间长度最大值为2一共有多少种拆法，然后从所有拆法中选取一个最小值，那么问题就解决了。
对于一个区间[l,r]我们可以枚举拆开的位置k(i<=k<j)，拆完后，如果长度还是很长，那么我们需要继续拆，这个时候我们发现原问题和子问题的问题是一样的，也就是子问题重叠了，我们可以考虑动态规划，现在我们先用递归解决这个问题。
那么我们一直拆一直拆，拆到这个区间 [ l , r ] ( l = r)，这个时候子问题无法继续分解也就是到达了递归出口，由题可知，一个独立的矩阵，它不需要乘，所以直接返回0即可。
那么这个问题就解决了。
代码：

#include<bits/stdc++.h>
using namespace std;
/* 4 50 10 40 30 5 */
const int maxn = 1e3 + 10;
int p[maxn];
const int inf = 0x3f3f3f3f;
int dfs(int l,int r){
	if(l == r)return 0;
	int res = inf;
	for(int k = l ; k < r ; k++){
		int ans = dfs(l,k) + dfs(k+1,r) + p[r] * p[l - 1] * p[k];
		res = min(res,ans);
	}
	return res;
}
int main(){
	int n;cin>>n;
	for(int i = 0; i <= n; i++)cin>>p[i];
	cout<<dfs(1,n);
}

DP版本
dp [ i ] [ j ] : 区间[i,j]的最小连乘数
转移方程：
dp [ i ] [ j ] = dp [ i ] [ k] + dp [ k + 1 ] [ j ] + p[ i - 1 ] * p[ j ] * p[ k ]
这个代码写起来有点多特殊，它是枚举的区间长度从[2,n]，然后它是斜对角线式计算子问题的。（一开始没有想到，就是只有从上到下做的，就出现调用子结果，但是子结果还没有计算的尴尬局面，枚举长度，斜对角线计算就不会出现这样的问题了。完美！）
代码：

#include<bits/stdc++.h>
using namespace std;
/* 4 50 10 40 30 5 */
const int maxn = 1e3 + 10;
int p[maxn];
const int inf = 0x3f3f3f3f;
int dp[maxn][maxn];
//dp[i][j]:区间[i,j]最少连乘次数 
int main(){
	int n;cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i = 0; i <= n; i++)cin>>p[i];
	for(int i = 0; i <= n; i++)dp[i][i] = 0;
	for(int len = 2; len <= n; len++){
		for(int i = 1; i <= n - len + 1; i++){
			int j = i + len - 1;
			for(int k = i; k <= j - 1 ;k++){
				dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[j]*p[k]*p[i-1] ,dp[i][j]);
			// cout<<"dp["<<i<<"]["<<j<<"] = "<<"dp["<<i<<"]["<<k<<"] + "<<"dp["<<k+1<<"]["<<j<<"] = "<<dp[i][j]<<endl; 
			}
		}
	}
	cout<<dp[1][n]<<endl;
}