这是我在编程比赛中遇到的一个有趣的问题：
问题陈述： 给定n矩阵的维数，确定是否存在使矩阵可以相乘的顺序。如果存在，则打印出所得矩阵的大小（尺寸的乘积）。
n
我的观察： 如果您将每个矩阵视为一个顶点并在可以相乘的矩阵之间绘制有向边，那么这将减少到NP完全哈密顿路径问题。我通过简单地强行解决问题来解决了这个问题，但这显然很慢。我想知道是否对此问题的特定实例进行了巧妙的优化。
为每个尺寸长度创建一个节点。也就是说，如果存在一个尺寸为（m，n）的矩阵，则m和n将是图中的顶点。
对于大小为（m，n）的每个矩阵，将节点m和n连接有向边（两个节点之间可以有多个边）。
现在找到一条欧拉步道将给出乘法顺序。
请参阅http://en.wikipedia.org/wiki/Euler_path以查找Eularian步道。复杂度非常接近线性（O（nlog ^ 3n loglogn），其中n是边数=矩阵数）。
