图中，描述了2x3矩阵与3x2矩阵相乘的过程，结果为2x2矩阵。如果pxq矩阵与qxr矩阵相乘，不难理解，总共做的乘法次数为qxqxr，因为最终得到pxr矩阵，每个值都是经过q次乘法得到。

所以axb矩阵，bxc矩阵，cxd矩阵，依次相乘，做乘法的次数为a*b*c+a*c*d=a*c*(b+d)，如果先将后面两个相乘，再与第一个相乘，则次数为b*d*(a+c)，由于矩阵相乘满足结合率，所以最终得到的矩阵相同，但做的乘法次数通常不同。

现在的问题就是，给定一组顺序固定的矩阵，并保证各个矩阵与左右的矩阵都可乘，如何知道最少使用多少次乘法操作，可以算出最终的矩阵？

比如考虑3个矩阵：a b c，是先乘a b，还是先乘b c呢？

这里将不讨论有哪些别的方法解决可以解决这个问题，先看一下递归解决这个问题会如何：
现在将规模扩大到5个矩阵：a b c d e如果不考虑效率，依次做以下五步计算：
1. 将ab相乘，递归计算axb c d e相乘需要的最小乘法次数min1；
2. 将bc相乘，递归计算a bxc d e相乘需要的最小乘法次数min2；
3. 将cd相乘，递归计算a b cxd e相乘需要的最小乘法次数min3；
4. 将de相乘，递归计算a b c dxe相乘需要的最小乘法次数min4；
5. min1 min2 min3 min4中最小的值，即为答案。

实际上，这种方法存在致命的效率问题，并且很快就会由于递归过深，导致栈空间不够用：

图中，用连接标出来一部分相同的问题，可以看出，这种方法需要重复解决已经解决的问题，问题的规模越大，这种对同一种问题重复解决的次数就越多。

感觉这种问题，有时候可能比较方便的通过标记，来说明一个问题是否之前已经解决过，但有些时候标记的方法也会失效，所以总觉得这种问题可以有种根本的解决方法，要不然稍微变换一下，又不知道从哪开始思考了。

请问对这种问题有比较深理解的朋友，可以指点一下吗？怎么来优化这个递归的过程？

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

上传的附件：

• matrix.png （1.84kb，1次下载）
• loop+recurse.png （5.91kb，11次下载）