动态规划矩阵连乘问题C++算法

1. 定义状态：设 $dp[i][j]$ 表示第 $i$ 个矩阵到第 $j$ 个矩阵的最小乘法次数。

2. 状态转移方程：对于每一组左右区间 $[i,j]$，枚举中间断点 $k$，将左右区间分为两个子问题，即 $[i,k]$ 和 $[k+1,j]$，则有：

$$dp[i][j]=\min_{i\leq k<j}\{dp[i][k]+dp[k+1][j]+p_{i-1}p_kp_j\}$$

其中 $p_{i-1}$ 表示第 $i-1$ 个矩阵的行数，$p_j$ 表示第 $j$ 个矩阵的列数，$p_k$ 表示第 $k$ 个矩阵的列数。

3. 边界条件：当 $i=j$ 时，$dp[i][j]=0$。

4. 最终答案：$dp[1][n]$。

5. 时间复杂度：$O(n^3)$。

代码实现如下：