矩阵连乘问题

• 问题：给定 $n$ 个矩阵序列 $A_1,A_2,\dots ,A_n$，求最少乘法次数。
• 状态定义：$m[i][j]$ 表示计算矩阵链 $A_{i\dots j}$ 所需的最少数乘次数。
• 转移方程： $m[i][j]={\min }_{i\le k<j}\{m[i][k]+m[k+1][j]+p_{i-1}{p}_k{p}_j\}$
  • $k$ 是断开位置（划分点）。
  • $p$ 数组存储维度：$A_i$ 的维度为 $p_{i-1}\times p_i$。
• 复杂度：时间 $O(n^3)$，空间 $O(n^2)$。
• 同构问题：凸多边形最优三角剖分 的递归结构与此完全一致。