Day 2：矩阵链相乘

我们熟知的是矩阵乘法满足结合律，也就是说对于三个矩阵A、B、C来说，(AB)C=A(BC)。这表明了矩阵乘法的结果与你所选择的计算顺序并无关系（在满足矩阵乘法要求的情况下）。很不幸的是，如果从计算机计算的角度来看就并非如此了。

矩阵链相乘

矩阵链相乘问题我们也可以称之为矩阵链排序问题，这是一个可以使用动态规划来解决的优化问题。在这个问题中我们给出一系列矩阵，目标是找到最有效的方法来乘以这些矩阵。 客观来讲这不是一个乘法问题，而是如何排列乘法顺序的问题。矩阵相乘的顺序会影响计算乘法所需的简单算术运算的数量，即计算复杂度。何为最有效？我们先来看个例子：

已知三个矩阵及其维度如下，A=[10,20], B=[20,30], C=[30,40], 不同的乘法顺序造成标量乘法的操作数差别很大

(AB)C=10*20*30 + 10*30*40 = 18000

A(BC)=20*30*40 + 10*20*40 = 32000

显然第一种方法我们称之为更有效的。我们可以进一步将矩阵链相乘问题考虑成如何给矩阵相乘加括号，使得一个大的优化问题被划分成多个子问题使得处理该问题的方法更有效。不容忽视的一点是以上所有的操作必须满足矩阵乘法的要求。

程序思路

针对矩阵链相乘，我们仍然利用递归的思想去解决这个问题。我们令函数MCM返回矩阵乘法的最小操作数，则MCM函数得到的结果就是矩阵链相乘所有可能排序中最优的那个。

问题

1、利用动态规划算法完成矩阵链相乘的算法复杂度是多少？

2、Python语言中zip函数的作用是什么？在Python 2和Python 3中有什么不同？